QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#646019 | #6303. Inversion | iorit | WA | 71ms | 68372kb | C++14 | 2.9kb | 2024-10-16 20:54:27 | 2024-10-16 20:54:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO {
// #if ONLINE_JUDGE
// #define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
// #else
#define getc() getchar()
// #endif
const int IL = 1 << 21, OL = 1 << 21;
int olen = 0;
char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
inline int read() {
int x;
cin >> x;
return x;
}
inline double readdb() {
register char ch = getc(); register double x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
if(ch == '.') {
register double b = 0.1;
ch = getc();
while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
}
return x * f;
}
inline int readstr(char *s) {
register char ch = getc(); register int len = 0;
while(!isalpha(ch)) ch = getc();
while(isalpha(ch)) s[++len] = ch, ch = getc();
return len;
}
inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
inline void putc(register char ch) { obuf[olen++] = ch; }
template<class T>
inline void write(register T x) {
if(x < 0) obuf[olen++] = '-', x = -x;
if(x > 9) write(x / 10);
obuf[olen++] = x % 10 + 48;
}
} using namespace IO;
const int N = 4e3 + 10;
int cnt = 0;
int ans[N][N];
bool cmp(int x, int y) {
// return 0;
int f = 0;
if(x > y) swap(x, y), f = 1;
if(x == y - 1) {
cnt++;
// return 0;
if(~ans[x][y]) return ans[x][y];
printf("? %d %d\n", x, y);
cout << endl;
fflush(stdout);
return ans[x][y] = read() ^ f;
}
// cnt+=4;
// return 0;
int res = f;
if(!~ans[x][y]) {
printf("? %d %d\n", x, y);
cout << endl;
fflush(stdout);
ans[x][y] = read();
}
res ^= ans[x][y];
if(!~ans[x+1][y]) {
printf("? %d %d\n", x+1, y);
cout << endl;
fflush(stdout);
ans[x+1][y] = read();
}
res ^= ans[x+1][y];
if(!~ans[x][y-1]) {
printf("? %d %d\n", x, y-1);
cout << endl;
fflush(stdout);
ans[x][y-1] = read();
}
res ^= ans[x][y-1];
if(!~ans[x+1][y-1]) {
if(x==y-2) ans[x+1][y-1] = 0;
else {printf("? %d %d\n", x+1, y-1);
cout << endl;
fflush(stdout);
ans[x+1][y-1] = read();
}
}
res ^= ans[x+1][y-1];
return res;
}
int p[N], tmp[N];
void solve(int l, int r) {
if(l == r) return;
// if(l==1) {
// puts("q");
// }
int mid = l + r >> 1;
solve(l, mid);
solve(mid + 1, r);
int i = l, j = mid + 1, k = i;
while(i <= mid && j <= r) {
if(cmp(p[i], p[j])) tmp[k++] = p[j++];
else tmp[k++] = p[i++];
}
while(i <= mid) tmp[k++] = p[i++];
while(j <= r) tmp[k++] = p[j++];
for(i = l; i <= r; i++) p[i] = tmp[i];
}
int id[N];
int main() {
int n;
memset(ans,-1,sizeof(ans));
n = read();
iota(p + 1, p + 1 + n, 1);
solve(1, n);
for(int i = 1; i <= n; i++)
id[p[i]] = i;
printf("! ");
for(int i = 1; i <= n; i++)
printf("%d ", id[i]);
fflush(stdout);
// cout << cnt << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 67320kb
input:
3 0 0 1
output:
? 1 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 71ms
memory: 68372kb
input:
1993 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 1...
output:
? 1 2 ? 3 4 ? 1 3 ? 2 3 ? 5 6 ? 7 8 ? 5 7 ? 6 7 ? 5 8 ? 6 8 ? 1 7 ? 2 7 ? 1 6 ? 2 6 ? 1 5 ? 2 5 ? 1 4 ? 2 4 ? 1 8 ? 2 8 ? 3 8 ? 3 7 ? 4 8 ? 4 7 ? 9 10 ? 11 12 ? 10 11 ? 9 11 ? 9 12 ? 10 12 ? 13 14 ? 15 16 ? 14 15 ? 13 15 ? 13 16 ? 14 16 ? 10 14 ? 11 14 ? 10 13 ...
result:
wrong output format Unexpected end of file - int32 expected