QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292051 | #6303. Inversion | QwertyPi# | WA | 65ms | 35100kb | C++17 | 1.8kb | 2023-12-27 16:42:23 | 2023-12-27 16:42:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) (a).size()
#define forn(i, n) for(int i = 0; i < (n); i++)
using namespace std;
const int N = 2e3 + 11;
int Q[N][N], query_cnt = 0;
int _query(int l, int r){
cout << "? " << l << ' ' << r << endl;
bool res; cin >> res;
return Q[l][r] = res;
}
int query(int l, int r){
if(l == r) return 0;
return Q[l][r] != -1 ? Q[l][r] : _query(l, r);
}
bool query2(int l, int r){ // a[l] > a[r]?
assert(l != r);
if(l > r) return !query2(r, l);
if(l + 1 == r) return query(l, r);
return query(l, r) ^ query(l + 1, r) ^ query(l, r - 1) ^ query(l + 1, r - 1);
}
int n;
void answer(vector<int> a){
assert(sz(a) == n + 1);
cout << "! ";
for(int i = 1; i <= n - 1; i++) cout << a[i] << ' ';
cout << a[n] << endl;
}
vector<int> G[N];
void add_edge(int u, int v){
G[u].push_back(v);
}
vector<int> tp;
bool vis[N];
void dfs(int v){
vis[v] = true;
for(auto u : G[v]){
if(!vis[u]) dfs(u);
}
tp.push_back(v);
}
void solve(){
cin >> n;
forn(i, n + 1) forn(j, n + 1) Q[i][j] = -1;
mt19937 rng(42);
for(int tr = 0; tr < 10000; tr++){
int u, v;
do{
u = rng() % n + 1, v = rng() % n + 1;
}while(u == v);
if(query2(u, v)){
add_edge(v, u);
}else{
add_edge(u, v);
}
}
vector<int> p(n + 1);
for(int i = 1; i <= n; i++)
if (!vis[i]) dfs(i);
for(int i = 0; i < n; i++){
p[tp[i]] = n - i;
}
answer(p);
}
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3636kb
input:
3 0 1 0
output:
? 1 3 ? 2 3 ? 1 2 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 65ms
memory: 35100kb
input:
1993 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1...
output:
? 65 1544 ? 66 1544 ? 65 1543 ? 66 1543 ? 575 1557 ? 576 1557 ? 575 1556 ? 576 1556 ? 289 1114 ? 290 1114 ? 289 1113 ? 290 1113 ? 1489 1514 ? 1490 1514 ? 1489 1513 ? 1490 1513 ? 519 581 ? 520 581 ? 519 580 ? 520 580 ? 583 1151 ? 584 1151 ? 583 1150 ? 584 1150 ? 806 1408 ? 807 1408 ? 806 1407 ? 807 1...
result:
wrong answer Wa.