QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#292055 | #6303. Inversion | QwertyPi# | WA | 55ms | 34892kb | C++17 | 1.4kb | 2023-12-27 16:45:27 | 2023-12-27 16:45:27 |
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;
}
void solve(){
cin >> n;
forn(i, n + 1) forn(j, n + 1) Q[i][j] = -1;
mt19937 rng(42);
vector<int> tp(n);
for(int i = 0; i < n; i++){
tp[i] = i + 1;
}
sort(all(tp), [](int u, int v){
return query2(u, v);
});
vector<int> p(n + 1);
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: 3564kb
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: 55ms
memory: 34892kb
input:
1993 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0...
output:
? 2 997 ? 3 997 ? 2 996 ? 3 996 ? 997 1993 ? 998 1993 ? 997 1992 ? 998 1992 ? 2 1993 ? 3 1993 ? 2 1992 ? 3 1992 ? 1 2 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 2 1991 ? 3 1991 ? 2 1990 ? 3 1990 ? 2 1989 ? 3 1989 ? 2 1988 ? 3 1988 ? 2 1987 ? 3 1987 ? 2 6 ? 3 6 ? 2 1986 ? 3 1986 ? 2 7 ? 3 7 ? 2 1985 ? 3 1985 ? ...
result:
wrong output format Unexpected end of file - int32 expected