QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#286701 | #6303. Inversion | 000226# | WA | 76ms | 19260kb | C++17 | 1.9kb | 2023-12-18 13:37:38 | 2023-12-18 13:37:38 |
Judging History
answer
#include <bits/stdc++.h>
#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define debug(...) fprintf (stderr, __VA_ARGS__)
using std :: cin;
using std :: cout;
using std :: endl;
using std :: cerr;
using i64 = long long;
const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline int add(int x, int y) { return mod(x + y - P); }
inline int dec(int x, int y) { return mod(x - y); }
inline int power(int x, int k) {
int res = 1; if (k < 0) k += P - 1;
while (k) { if (k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; }
return res;
}
int qry (int l, int r) {
if (l == r) return 0;
if (l > r) return 0;
cout << "? " << l << ' ' << r << endl;
int o;
cin >> o;
return o;
}
const int N = 2000 + 5;
int n;
int ans[N], dans[N];
int f[N][N];
inline int query (int l, int r) { // l > r
int o = 0;
if (l > r) std :: swap (l, r), o ^= 1;
if (f[l][r] == -1) f[l][r] = qry (l, r);
if (f[l + 1][r] == -1) f[l + 1][r] = qry (l + 1, r);
if (f[l][r - 1] == -1) f[l][r - 1] = qry (l, r - 1);
if (f[l + 1][r - 1] == -1) f[l + 1][r - 1] = qry (l + 1, r - 1);
return f[l][r] ^ f[l + 1][r] ^ f[l][r - 1] ^ f[l + 1][r - 1] ^ o;
}
int main() {
std :: ios :: sync_with_stdio(false);
srand (time(0));
cin >> n;
lep (i, 1, n) lep (j, 1, n) f[i][j] = -1;
ans[1] = 1;
for (int i = 2; i <= n; i ++) {
int l = 1, r = i - 1, res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (query (ans[mid], i)) r = mid - 1;
else res = mid, l = mid + 1;
}
rep (j, i, res + 2) ans[j] = ans[j - 1];
ans[res + 1] = i;
}
lep (i, 1, n) dans[ans[i]] = i;
cout << "! ";
for (int i = 1; i <= n; i ++) cout << dans[i] << ' '; cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3652kb
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: 76ms
memory: 19260kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 1 4 ? 2 6 ? 3 6 ? 5 6 ? 1 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 3 8 ? 4 8 ? 3 7 ? 4 7 ? 1 9 ? 2 9 ? 8 9 ? 3 9 ? 9 10 ? 5 10 ? 6 10 ? 5 9 ? 6 9 ? 7 10 ? 8 10 ? 7 9 ? 1 11 ? 2 11 ? 1 10 ? 2 10 ? 8 11 ? 9 11 ? 10 11 ? 11 12 ? 8 12 ? 9 12 ? 10 12 ? 2 1...
result:
wrong output format Unexpected end of file - int32 expected