noip 2022 第二题喵了个喵 meow 在 Lemon LemonLime 中 SPJ Special Judge 测评配置设置

article/2025/9/26 22:45:38

比赛目录如下：

用户程序(meow.cpp)如下：

#include <bits/stdc++.h>
using namespace std;template<typename T>
inline void read(T &x) {x = 0; char ch = getchar();bool f = 0;while (!isdigit(ch)) f |= ch == '-', ch = getchar();while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();if (f) x = -x;
}
template<typename T>
inline void write(T x, char c) {if (x == 0) {putchar('0'), putchar(c);return;}static int stk[20];int top = 0;while (x) stk[++top] = x % 10, x /= 10;while (top) putchar('0' + stk[top--]);putchar(c);
}const int N = 605, M = 4000005;
int T, n, m, k, a[M], bel[N], stk[N], top;
int op[M], x[M], y[M], tot, cur[N];
vector<int> b[N];inline void push1(int x) {op[++tot] = 1;::x[tot] = x;
}
inline void push2(int x, int y) {op[++tot] = 2;::x[tot] = x, ::y[tot] = y;
}inline int get_pos(int x) {return b[bel[x]][0] == x ? 1 : 2;
}
inline void popBack(int pos) {int x = b[pos].back();b[pos].pop_back();bel[x] = 0;stk[++top] = pos;
}
inline void popFront(int pos) {int x = b[pos][0];b[pos].erase(b[pos].begin());bel[x] = 0;stk[++top] = pos;
}void solve() {read(n), read(m), read(k);for (int i = 1; i <= m; ++i) read(a[i]);if (n == 1) {write(m, '\n');for (int i = 1; i <= m; ++i) write(1, ' '), write(1, '\n');return;}for (int i = 1; i <= n; ++i) b[i].clear();for (int i = 1; i <= k; ++i) bel[i] = 0;top = tot = 0; for (int i = 1; i < n; ++i) stk[++top] = i, stk[++top] = i;int empty_pos = n;for (int p = 1; p <= m; ) {int x = a[p];if (bel[x]) {if (get_pos(x) == 1) {push1(empty_pos);push2(bel[x], empty_pos);popFront(bel[x]);} else {push1(bel[x]);popBack(bel[x]);}++p;} else if (top) {bel[x] = stk[top--];push1(bel[x]);b[bel[x]].push_back(x);++p;} else {push1(-1);int tmp = tot;int pos = -1;int p1 = ++p;for (; p1 <= m; ++p1) {int y = a[p1];if (y == x) {break;} else {int b = bel[y];if (get_pos(y) == 2) {cur[b] ^= 1;} else {pos = b;break;}}}if (pos == -1) {::x[tmp] = empty_pos;for (int i = p; i < p1; ++i) {int y = a[i], b = bel[y];push1(b);}push1(empty_pos);for (int i = p1 - 1; i >= p; --i) {int y = a[i], b = bel[y];if (cur[b]) {popBack(b);cur[b] = 0;}}} else if (cur[pos] == 1) {::x[tmp] = empty_pos;bel[x] = empty_pos;b[empty_pos].push_back(x);for (int i = p; i <= p1; ++i) {int y = a[i], b = bel[y];push1(b);}popBack(pos), popBack(pos);top -= 2;cur[pos] = 0;for (int i = p1 - 1; i >= p; --i) {int y = a[i], b = bel[y];if (cur[b]) {popBack(b);cur[b] = 0;}}stk[++top] = empty_pos;empty_pos = pos;} else {::x[tmp] = pos;for (int i = p; i < p1; ++i) {int y = a[i], b = bel[y];push1(b == pos ? empty_pos : b);}for (int i = p1 - 1; i >= p; --i) {int y = a[i], b = bel[y];if (cur[b]) {popBack(b);cur[b] = 0;}}push1(empty_pos);push2(pos, empty_pos);bel[b[pos][0]] = 0;b[pos][0] = b[pos][1];b[pos][1] = x;bel[x] = pos;}p = p1 + 1;}   } write(tot, '\n');for (int i = 1; i <= tot; ++i) {write(op[i], ' ');if (op[i] == 1) {write(x[i], '\n');} else {write(x[i], ' ');write(y[i], '\n');}}
}int main() {freopen("meow.in", "r", stdin);freopen("meow.out", "w", stdout);read(T);while (T--) solve();return 0;
}

SPJ代码(chk.cpp)如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <deque>
#define STR_SIZE 10000int a[2222222];
std::deque<int> q[333];int specialJudge(FILE *in, FILE *out, FILE *ans){
// TODO: write your special judge hereint T;fscanf(in, "%d", &T);while(T--){int n,m,k;fscanf(in, "%d%d%d", &n,&m,&k);for(int i=1;i<=m;++i){fscanf(in, "%d", a+i);}int now=1;int op;if(fscanf(out, "%d", &op)!=1){return 0;}if(op<m||op>2*m){return 0;}for(int i=1;i<=op;++i){int v,s1,s2;if(fscanf(out, "%d", &v)!=1){return 0;}if(v==1){if(fscanf(out, "%d", &s1)!=1){return 0;}if(s1<=0||s1>n){return 0;}if(now<=m){if(!q[s1].empty()&&a[now]==q[s1].back()){q[s1].pop_back();}else{q[s1].push_back(a[now]);}++now;}}else if(v==2){if(fscanf(out, "%d%d", &s1, &s2)!=2){return 0;}if(s1<=0||s1>n||s2<=0||s2>n||s1==s2){return 0;}if(!q[s1].empty()&&!q[s2].empty()&&q[s1].front()==q[s2].front()){q[s1].pop_front();q[s2].pop_front();}}else return 0;}if(now<=m){return 0;}for(int i=1;i<=n;++i){if(q[i].size()){return 0;}}}return 1;
}
int main(int argc,char *argv[]){FILE * f_in=fopen(argv[1],"r");//标准输入 fpinFILE * f_out=fopen(argv[2],"r");//用户输入 fpoutFILE * f_std=fopen(argv[3],"r");//标准输出 fpansint score=atoi(argv[4]);//单个测试点分值FILE * f_score=fopen(argv[5],"w");//得分文件 FILE * f_report=fopen(argv[6],"w");//报告文件 /* compare the contents */if (specialJudge(f_in, f_out, f_std)){fprintf(f_report,"Right Output!!!");fprintf(f_score,"%d",score);}else{fprintf(f_report,"Wrong Answer");fprintf(f_score,"%d",0);}return 0; 
}

未加SPJ，测评如下：