QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333613 | #6303. Inversion | automac | WA | 114ms | 7324kb | C++20 | 2.3kb | 2024-02-20 10:09:48 | 2024-02-20 10:09:49 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r) for(int i = (int)l; i <= (int)r; ++i)
#define fored(i, l, r) for(int i = (int)r; i >= (int)l; --i)
#define all(x) x.begin(), x.end()
#define el '\n'
#define d(x) cerr << #x << ' ' << x << el
#define sz(a) (int) a.size()
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int,int> ii;
typedef tuple<ll,int,int> iii;
const int nax = 2e5;
// const int nax = 2e3;
const ll inf = 1e17;
// void show(vi &v){
// for(int x : v)cout<<x<<" ";
// cout<<el;
// }
map<ii, int> queries;
bool find(int i, int j){
if(i==j)return 0;
assert(i< j);
if(queries.find({i,j}) != queries.end()){
return queries[{i,j}];
}
cout<<"? "<<i<<" "<<j<<endl;
bool parity;
cin>>parity;
queries[{i,j}] = parity;
return parity;
}
bool isGreater(int i, int j){
if(abs(j-i) == 1) return find(i,j);
assert(i < j);
int allRange = find(i, j);
int excL = find(i+1, j), excR = find(i, j-1);
int excAll = find(i+1, j-1);
if(((excL + excR - excAll + 2) % 2) != allRange) return 1;
return 0;
}
void solve(){
int n;
cin>>n;
if(n == 1){
cout<<"! 1"<<endl;
return ;
}
vi v(n);
iota(all(v), 1);
if(isGreater(v[0],v[1])) swap(v[0], v[1]);
fore(i,2,n-1){
int lo = -1, hi = i;
while(lo + 1 < hi){
int mid = lo + (hi-lo)/2;
if(isGreater(v[mid], v[i])){
hi = mid;
}else lo = mid;
}
// d(hi);
// show(v);
fored(j, hi, i-1){
swap(v[j], v[j+1]);
}
// show(v);
}
vi ans(n);
forn(i,n){
ans[v[i]-1] = i+1;
}
cout<<"! ";
forn(i,n){
cout<<ans[i];
if(i!=n-1) cout<<" ";
}
cout<<endl;
}
int main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
int tt = 1;
// cin>>tt;
while(tt--){
solve();
}
}
/**
* aprendizaje:
* Fijar 2 elementos y pensar como ordenarlos. Pensar en reducir la cantidad de consultas
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
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: 114ms
memory: 7324kb
input:
1993 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1...
output:
? 1 2 ? 1 3 ? 2 3 ? 2 4 ? 3 4 ? 2 5 ? 3 5 ? 1 5 ? 1 4 ? 2 6 ? 3 6 ? 5 6 ? 1 6 ? 1 7 ? 2 7 ? 5 7 ? 6 7 ? 1 8 ? 2 8 ? 3 8 ? 4 8 ? 3 7 ? 4 7 ? 1 9 ? 2 9 ? 8 9 ? 3 9 ? 9 10 ? 5 10 ? 6 10 ? 5 9 ? 6 9 ? 7 10 ? 8 10 ? 7 9 ? 1 11 ? 2 11 ? 1 10 ? 2 10 ? 8 11 ? 9 11 ? 10 11 ? 11 12 ? 8 12 ? 9 12 ? 10 12 ? 2 1...
result:
wrong output format Unexpected end of file - int32 expected