QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303553 | #6303. Inversion | ucup-team052# | WA | 1ms | 3752kb | C++14 | 1.7kb | 2024-01-12 18:20:39 | 2024-01-12 18:20:39 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=2005;
int n,a[N],suf[N];
int main(){
rd(n);
vector<int>order;
rep(i,1,n){
int l=0,r=SZ(order)-1,ret=-1;
rep(i,0,SZ(order)-1)a[order[i]]=i;
per(j,i-1,1){
if(j<i-1)suf[j]=suf[j+1];
else suf[j]=0;
rep(k,j+1,i-1)suf[j]^=a[j]>a[k];
}
auto query=[&](int l,int r){
if(r==i){
printf("? %d %d\n",l,r);
fflush(stdout);
int x;
scanf("%d",&x);
return x;
}else{
assert(r==i-1);
/*int x=0;
rep(j,l,r)rep(k,j+1,r)x^=a[j]>a[k];
assert(suf[l]==x);
return suf[l];*/
}
};
auto cmp=[&](int l,int r){
return query(l,r)^query(l,r-1)^query(l+1,r)^query(l+1,r-1)^1;
};
while(l<=r){
int mid=(l+r)>>1;
if(cmp(order[mid],i)){
ret=mid;
l=mid+1;
}else{
r=mid-1;
}
}
order.insert(order.begin()+(ret+1),i);
DD(order);
}
rep(i,0,SZ(order)-1)a[order[i]]=i;
printf("! ");
rep(i,1,n)printf("%d ",a[i]+1);
fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3752kb
input:
3 0 1
output:
? 1 2 ? 2 3 ! 3 2 1
result:
wrong answer Wa.