QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#332816 | #6303. Inversion | Scano | RE | 1ms | 3600kb | C++20 | 1.8kb | 2024-02-19 16:07:08 | 2024-02-19 16:07:09 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(v) v.size()
#define forn(i,n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define el endl
#define all(v) v.begin(),v.end()
#define pb push_back
#define d(x) cout << #x << " : " << x << el
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef tuple<ll,int,int> iii;
int dr[] = {1,0,-1,0};
int dc[] = {0,1,0,-1};
const int nax = 1e5 + 20;
vector<int> arr;
int preguntas = 0;
int get(int l, int r){
if(l == r) return 0;
++preguntas;
assert(preguntas <= 4e4);
cout << "? " << l + 1 << " " << r + 1 << el;
int x;
cin >> x;
return x;
}
int ask(int l, int r){
if(l+1==r){
return get(l, r);
}
int vlr = get(l, r);
int vl_r = get(l+1,r);
int vlr_ = get(l, r-1);
int vl_r_ = get(l+1, r-1);
return ((vlr - vl_r - vlr_ + vl_r_)%2 + 2)%2;
}
void solve(vector<int> &pos, int start = 0){
int r = random()%sz(pos);
vector<int> ls, rs;
int cnt = 0;
forn(i,sz(pos)){
if(i == r) continue;
int val = 0;
if(i < r){
val = ask(pos[i], pos[r]);
if(val == 0){
++cnt;
ls.pb(pos[i]);
}else{
rs.pb(pos[i]);
}
}else{
val = ask(pos[r], pos[i]);
if(val == 1){
ls.pb(pos[i]);
++cnt;
}else{
rs.pb(pos[i]);
}
}
}
arr[pos[r]] = start + 1 + cnt;
if(sz(ls)) solve(ls, start);
if(sz(rs)) solve(rs, arr[pos[r]]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cout << setprecision(20)<< fixed;
int n;
cin >> n;
arr.resize(n);
vector<int> pos;
forn(i,n){
pos.pb(i);
}
solve(pos);
cout << "! ";
forn(i,n){
cout << arr[i] << " ";
}
cout << el;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
3 0 1 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 1 2 ! 2 3 1
result:
ok OK, guesses=5
Test #2:
score: -100
Runtime Error
input:
1993 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0...
output:
? 1 575 ? 2 575 ? 1 574 ? 2 574 ? 2 575 ? 3 575 ? 2 574 ? 3 574 ? 3 575 ? 4 575 ? 3 574 ? 4 574 ? 4 575 ? 5 575 ? 4 574 ? 5 574 ? 5 575 ? 6 575 ? 5 574 ? 6 574 ? 6 575 ? 7 575 ? 6 574 ? 7 574 ? 7 575 ? 8 575 ? 7 574 ? 8 574 ? 8 575 ? 9 575 ? 8 574 ? 9 574 ? 9 575 ? 10 575 ? 9 574 ? 10 574 ? 10 575 ?...