QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106093 | #6303. Inversion | Melacau | WA | 237ms | 11304kb | C++17 | 3.2kb | 2023-05-16 15:04:51 | 2023-05-16 15:04:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using db = double;
using s64 = long long;
using ld = long double;
using u32 = unsigned int;
using u64 = unsigned long long;
using vi = vector<int>;
using vii = vector<vi>;
using vll = vector<s64>;
using pii = pair<int, int>;
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define For(i, a, b) for (decay<decltype(b)>::type i = (a), _##i = (b); i <= _##i; ++i)
#define Ford(i, a, b) for (decay<decltype(a)>::type i = (a), _##i = (b); i >= _##i; --i)
#define FOR(i, a, b) for (decay<decltype(b)>::type i = (a), _##i = (b); i < _##i; ++i)
#define FORD(i, a, b) for (decay<decltype(a)>::type i = (a) - 1, _##i = (b); i >= _##i; --i)
#ifdef LOCAL
#define Debug(x...) do { cerr << "\033[32;1m" << #x << " -> "; Err(x); } while (0)
void Err() { cerr << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void Err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; Err(x...); }
template<typename T, typename... A>
void Err(T a, A... x) { cerr << a << ' '; Err(x...); }
#else
#define Debug(...)
#endif
#define all(x) x.begin(), x.end()
const double PI = acos(-1);
const double eps = 1e-7;
namespace Modulo {
// const int P = 998244353;
const int P = 1e9 + 7;
int Add(int x, int y) {return (x += y) >= P ? x - P : x;}
int Dec(int x, int y) {return (x -= y) < 0 ? x + P : x;}
int Mult(int x, int y) {return (s64) x * y % P;}
void mult(int &x, int y) {x = (s64) x * y % P;}
void add(int &x, int y) {if ((x += y) >= P) x -= P;}
void dec(int &x, int y) {if ((x -= y) < 0) x += P;}
int qpw(int x, int k = P - 2) {
int res = 1;
for (; k; k >>= 1, mult(x, x))
if (k & 1) mult(res, x);
return res;
}
}
namespace Solver {
// const char endl = '\n';
const int N = 2005;
int ord[N], pos[N];
bool cnt[N][N], vis[N][N];
bool query(int x, int y) {
if (!vis[x][y]) {
cout << "? " << x << ' ' << y << endl;
cin >> cnt[x][y];
vis[x][y] = true;
}
if (x + 1 == y) return cnt[x][y] ^ 1;
if (!vis[x + 1][y]) {
cout << "? " << x + 1 << ' ' << y << endl;
cin >> cnt[x + 1][y];
vis[x + 1][y] = true;
}
return cnt[x][y] ^ cnt[x + 1][y] ^ cnt[x][y - 1] ^ cnt[x + 1][y - 1] ^ 1;
}
void main() {
int n; cin >> n;
ord[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j)
pos[ord[j]] = j;
int l = 1, r = i;
while (l < r) {
int mid = l + r >> 1;
if (query(pos[mid], i)) l = mid + 1;
else r = mid;
}
// cerr << i << ' ' << l << endl;
for (int j = l; j < i; ++j)
ord[pos[j]] = j + 1;
ord[i] = l;
for (int j = i - 1; j; --j)
cnt[j][i] = cnt[j + 1][i] ^ (ord[j] > ord[i]);
}
cout << '!';
for (int i = 1; i <= n; ++i)
cout << ' ' << ord[i];
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
For(_t, 1, T) {
// cout << "Case #" << _t << ": ";
// cout << endl;
Solver::main();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5380kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 237ms
memory: 11304kb
input:
1993 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1...
output:
? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 3 5 ? 4 5 ? 2 5 ? 1 5 ? 2 6 ? 3 6 ? 1 6 ? 5 6 ? 2 7 ? 3 7 ? 4 7 ? 5 7 ? 2 8 ? 3 8 ? 6 8 ? 7 8 ? 5 8 ? 2 9 ? 3 9 ? 6 9 ? 7 9 ? 1 9 ? 9 10 ? 6 10 ? 7 10 ? 1 10 ? 2 10 ? 9 11 ? 10 11 ? 6 11 ? 7 11 ? 11 12 ? 3 12 ? 4 12 ? 2 12 ? 9 12 ? 10 12 ? 12 13 ? 3 13 ? 4 13 ? 2 13 ? 9 13 ...
result:
wrong answer Wa.