QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#303546 | #6303. Inversion | ucup-team052# | WA | 181ms | 3800kb | C++14 | 1.6kb | 2024-01-12 18:10:27 | 2024-01-12 18:10:28 |
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];
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;
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{
int x=0;
rep(i,l,r)rep(j,l+1,r){
x+=a[i]>a[j];
}
return x;
}
};
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3 0 0 0 1
output:
? 1 2 ? 2 2 ? 1 3 ? 2 3 ! 2 3 1
result:
ok OK, guesses=4
Test #2:
score: -100
Wrong Answer
time: 181ms
memory: 3800kb
input:
1993 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0...
output:
? 1 2 ? 2 2 ? 1 3 ? 2 3 ? 2 3 ? 3 3 ? 2 4 ? 3 4 ? 3 4 ? 4 4 ? 2 5 ? 3 5 ? 3 5 ? 4 5 ? 5 6 ? 6 6 ? 3 6 ? 4 6 ? 4 6 ? 5 6 ? 5 7 ? 6 7 ? 1 7 ? 2 7 ? 2 7 ? 3 7 ? 5 8 ? 6 8 ? 6 8 ? 7 8 ? 4 8 ? 5 8 ? 5 9 ? 6 9 ? 6 9 ? 7 9 ? 4 9 ? 5 9 ? 8 9 ? 9 9 ? 3 10 ? 4 10 ? 4 10 ? 5 10 ? 9 10 ? 10 10 ? 3 11 ? 4 11 ? 1...
result:
wrong answer Wa.