QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#257573 | #6303. Inversion | Crying | WA | 50ms | 17348kb | C++17 | 1.2kb | 2023-11-19 10:24:59 | 2023-11-19 10:24:59 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 2010;
int n,p[MAXN],f[MAXN][MAXN];
int query(int l,int r){
if(l>=r)return 0;
cout<<"? "<<l<<" "<<r<<endl;
int ret; cin>>ret;
return ret;
}
int chk(int j,int i){ //check whether p[j] < p[i]
int r = f[j+1][i-1] ^ f[j][i-1] ^ query(j+1,i) ^ query(j,i);
return !r;
}
int main(){
cin>>n;
p[1] = 1;
//
rep(i,2,n){
int L = 1,R = i-1,ret = 0;
while(L<=R){
int mid = (L+R)>>1,j = -1;
rep(k,1,i-1)if(p[k]==mid){j=k;break;} assert(j!=-1);
if(chk(j,i)){
ret = mid;L = mid+1;
}else{
R = mid-1;
}
}
p[i] = ret+1;
rep(j,1,i-1)if(p[j] > ret)p[j]++;
int sum = 0;
per(j,i-1,1){
sum += (p[j]>p[i]);
f[j][i] = f[j][i-1]+sum;
}
}
//
cout<<"! "; rep(i,1,n)cout<<p[i]<<" ";cout<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3700kb
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: 50ms
memory: 17348kb
input:
1993 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0...
output:
? 1 2 ? 2 3 ? 1 3 ? 2 3 ? 3 4 ? 2 4 ? 3 4 ? 3 5 ? 2 5 ? 2 5 ? 1 5 ? 3 6 ? 2 6 ? 5 6 ? 2 6 ? 1 6 ? 2 7 ? 1 7 ? 6 7 ? 5 7 ? 2 8 ? 1 8 ? 6 8 ? 5 8 ? 7 8 ? 7 9 ? 6 9 ? 8 9 ? 8 9 ? 7 9 ? 7 10 ? 6 10 ? 9 10 ? 8 10 ? 7 10 ? 6 11 ? 5 11 ? 10 11 ? 10 11 ? 9 11 ? 6 12 ? 5 12 ? 11 12 ? 10 12 ? 9 12 ? 9 13 ? 8 ...
result:
wrong answer Wa.