QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#316972 | #6303. Inversion | Network_Error | WA | 47ms | 11044kb | C++14 | 3.4kb | 2024-01-28 09:11:57 | 2024-01-28 09:11:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
// #define int long long
namespace IO {
#define BF 65536
char buf[BF], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BF, stdin), p1 == p2) ? EOF : *p1++)
// template<typename T>
inline int uread() {
int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x;
}
// template<typename T>
inline int read() {
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return f ? -x : x;
}
char obuf[BF + 30]; int o1, o2, num[30];
#define flush() fwrite(obuf, 1, o1, stdout), o1 = 0
inline void putchar(const char &c) {
obuf[o1++] = c; if (o1 >= BF) flush();
}
// template<typename T>
inline void uwrite(int x) {
do num[++o2] = x % 10; while (x /= 10);
do obuf[o1++] = num[o2] ^ 48; while (--o2); obuf[o1++] = '\n'; if (o1 >= BF) flush();
}
// template<typename T>
inline void write(const int& x) {
if (x < 0) obuf[o1++] = '-', uwrite(-x); else uwrite(x);
}
} using namespace IO;
namespace Maths {
const int mod = 998244353;
int power(int x, int y) {
int ans = 1; while (y) {
if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
} return ans;
}
int power(int x, int y, int mod) {
int ans = 1; while (y) {
if (y & 1) ans = 1ll * ans * x % mod; y >>= 1; x = 1ll * x * x % mod;
} return ans;
}
int fac[1000010], inv[1000010];
void init() {
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= 1e6; i++) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
for (int i = 2; i <= 1e6; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
int binom(int n, int m) {
return n < m || m < 0 ? 0 : 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}
} using namespace Maths;
namespace Loser {
int n;
short ans[2010][2010];
int ask(int l, int r) {
if (l > r) swap(l, r);
if (l == r) return 0;
if (ans[l][r]) return ans[l][r] - 1;
cout << "? " << l << ' ' << r << endl; int x; cin >> x; ans[l][r] = x + 1; return x;
}
int a[2010], pos[2010], rev[2010];
int cmp(int l, int r) {
// deb(l),deb(r)<<'\n';
if (l == 0) return 0;
// return ask(l,r)^ask(l+1,r)^ask(l,r-1)^ask(l+1,r-1);
return rev[l] ^ rev[l + 1] ^ ask(l, r) ^ ask(l + 1, r);
}
void main() {
cin >> n;
pos[1] = 1;
for (int i = 2; i <= n; i++) {
int l = 0, r = i - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (cmp(pos[mid], i)) r = mid - 1; else l = mid;
}
for (int k = i; k > l + 1; k--) pos[k] = pos[k - 1]; pos[l + 1] = i;
for (int k = 1; k <= i; k++) a[pos[k]] = k;
for (int k = i, s = 0; k >= 1; k--) rev[i] ^= s, s ^= a[k] > a[i];
// deb(l);for(int k=1;k<=i;k++)cout<<pos[k]<<' ';cout<<'\n';
}
cout << "! "; for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl;
}
}
signed main() {
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T = 1; while (T--) Loser::main(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 47ms
memory: 11044kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 1 0 0...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 2 6 ? 3 6 ? 4 6 ? 5 6 ? 2 7 ? 3 7 ? 5 7 ? 6 7 ? 2 8 ? 3 8 ? 5 8 ? 6 8 ? 7 8 ? 1 9 ? 2 9 ? 7 9 ? 8 9 ? 5 9 ? 6 9 ? 1 10 ? 2 10 ? 3 10 ? 4 10 ? 5 10 ? 6 10 ? 7 10 ? 1 11 ? 2 11 ? 4 11 ? 5 11 ? 3 11 ? 2 12 ? 3 12 ? 4 12 ? 5 12 ? 10 12 ? 11 12 ? 6 12 ? 7...
result:
wrong answer Wa.