QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798172 | #1458. Binary Search Algorithm | Kazemaru | WA | 158ms | 76016kb | C++17 | 990b | 2024-12-04 09:07:25 | 2024-12-04 09:07:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e5,M=8765;
int a[N],b[N],p[N],x,y,z;string O;bool P[M][M];
inline int Q(int x,int y){return!a[y]||P[a[x]][a[y]];}
inline void put(int x){if(x)b[++m]=x;}
inline void pvt(int x){put(a[x]);put(a[x*2]);put(a[x*2+1]);}
inline void ask(){
sort(b+1,b+m+1);m=unique(b+1,b+m+1)-b-1;
cout<<m;f(i,1,m)cout<<" "<<b[i];cout<<endl;
f(i,1,m)cin>>b[i];
f(i,1,m)f(j,i,m)P[b[i]][b[j]]=1;m=0;
}
inline void mv(int x,int y){swap(a[x],a[y]);p[a[x]]=x;p[a[y]]=y;}
#define h(u,P)for(x=l;(y=x/2,z=x*2+Q(x*2+1,x*2),(x&&x<=n))&&P;x=u)
signed main(){
cin>>s;a[0]=s+1;
f(_,1,s*2){
cin>>O>>l;
if(O[0]=='a'){
a[p[l]=++n]=l;l=n;
h(y,1)pvt(x);ask();
h(y,Q(x,y))mv(x,y);
}else{
mv(l=p[l],n);a[n--]=0;
h(z,1)pvt(x);ask();
h(z,Q(z,x))mv(x,z);
}
cout<<(n?a[1]:-1)<<endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9832kb
input:
3 add 1 1 add 3 3 1 delete 1 add 2 3 2 delete 3 2 delete 2
output:
1 1 1 2 1 3 3 0 3 2 2 3 3 1 2 2 0 -1
result:
ok n=3, OK
Test #2:
score: 0
Accepted
time: 2ms
memory: 9788kb
input:
10 add 9 9 add 4 9 4 add 6 9 4 6 delete 9 4 6 add 7 7 4 6 delete 4 add 5 7 5 6 add 8 7 5 8 6 add 10 7 10 5 8 6 delete 8 add 3 3 7 10 5 6 add 2 3 7 5 2 delete 6 2 delete 10 delete 7 2 add 1 3 1 5 2 delete 1 2 delete 3 5 2 delete 5 2 delete 2
output:
1 9 9 2 4 9 9 3 4 6 9 9 2 4 6 4 3 4 6 7 7 0 7 3 5 6 7 7 4 5 6 7 8 7 5 5 6 7 8 10 7 0 7 5 3 5 6 7 10 3 4 2 3 5 7 3 1 2 3 0 3 1 2 3 4 1 2 3 5 3 1 2 3 2 2 5 5 1 2 2 0 -1
result:
ok n=10, OK
Test #3:
score: 0
Accepted
time: 2ms
memory: 10156kb
input:
100 add 81 81 add 96 81 96 add 94 81 94 96 add 32 81 94 32 96 add 35 81 94 32 35 96 add 59 81 94 32 59 add 50 81 50 94 32 59 add 57 81 50 57 32 35 96 add 39 39 81 50 57 32 35 96 add 55 39 81 50 57 35 55 add 23 39 81 50 57 23 35 55 add 40 39 81 50 40 94 59 add 5 39 81 50 40 94 59 5 add 2 39 81 50 40 ...
output:
1 81 81 2 81 96 81 3 81 94 96 81 4 32 81 94 96 81 5 32 35 81 94 96 81 4 32 59 81 94 81 5 32 50 59 81 94 81 6 32 35 50 57 81 96 81 7 32 35 39 50 57 81 96 39 6 35 39 50 55 57 81 39 7 23 35 39 50 55 57 81 39 6 39 40 50 59 81 94 39 7 5 39 40 50 59 81 94 39 6 2 39 40 50 81 94 39 1 2 39 6 12 39 40 50 81 9...
result:
ok n=100, OK
Test #4:
score: 0
Accepted
time: 0ms
memory: 10100kb
input:
100 add 71 71 add 75 71 75 add 43 43 71 75 add 69 43 71 69 75 add 55 43 71 69 55 75 add 89 43 71 89 69 add 31 43 71 89 69 31 add 52 43 71 69 55 52 75 add 24 24 43 71 69 55 52 75 add 6 24 43 71 6 69 55 add 9 24 43 71 6 69 55 9 add 62 24 43 71 89 62 31 add 19 24 43 71 89 62 31 19 add 35 24 43 71 35 89...
output:
1 71 71 2 71 75 71 3 43 71 75 43 4 43 69 71 75 43 5 43 55 69 71 75 43 4 43 69 71 89 43 5 31 43 69 71 89 43 6 43 52 55 69 71 75 43 7 24 43 52 55 69 71 75 24 6 6 24 43 55 69 71 24 7 6 9 24 43 55 69 71 24 6 24 31 43 62 71 89 24 7 19 24 31 43 62 71 89 24 6 24 31 35 43 71 89 24 7 24 31 35 38 43 71 89 24 ...
result:
ok n=100, OK
Test #5:
score: 0
Accepted
time: 14ms
memory: 16312kb
input:
1000 add 93 93 add 917 93 917 add 921 93 917 921 add 70 93 917 921 70 add 949 93 949 917 921 70 add 777 93 949 777 921 add 237 93 949 777 237 921 add 581 581 93 949 777 917 70 add 461 581 93 949 777 917 70 461 add 319 581 93 949 777 917 319 add 42 581 93 949 777 42 917 319 add 690 581 93 690 777 237...
output:
1 93 93 2 93 917 93 3 93 917 921 93 4 70 93 917 921 93 5 70 93 917 921 949 93 4 93 777 921 949 93 5 93 237 777 921 949 93 6 70 93 581 777 917 949 581 7 70 93 461 581 777 917 949 581 6 93 319 581 777 917 949 581 7 42 93 319 581 777 917 949 581 6 93 237 581 690 777 921 581 7 93 237 581 631 690 777 921...
result:
ok n=1000, OK
Test #6:
score: 0
Accepted
time: 4ms
memory: 15464kb
input:
1000 add 589 589 add 844 589 844 add 341 589 341 844 add 362 589 341 844 362 add 955 955 589 341 844 362 add 565 955 589 565 341 add 467 955 589 565 341 467 add 664 955 589 565 844 664 362 add 167 167 955 589 565 844 664 362 add 879 167 955 589 565 844 879 add 934 167 934 955 589 565 844 879 add 757...
output:
1 589 589 2 589 844 589 3 341 589 844 589 4 341 362 589 844 589 5 341 362 589 844 955 955 4 341 565 589 955 955 5 341 467 565 589 955 955 6 362 565 589 664 844 955 955 7 167 362 565 589 664 844 955 167 6 167 565 589 844 879 955 167 7 167 565 589 844 879 934 955 167 6 167 341 467 565 757 934 167 7 16...
result:
ok n=1000, OK
Test #7:
score: 0
Accepted
time: 115ms
memory: 75060kb
input:
8000 add 2497 2497 add 827 827 2497 add 4801 827 4801 2497 add 2709 827 4801 2709 2497 add 4516 827 4801 2709 4516 2497 add 656 827 656 4801 2709 add 4773 4773 827 656 4801 2709 add 1444 4773 827 1444 2709 4516 2497 add 2338 4773 827 1444 2709 4516 2338 2497 add 1254 4773 827 1444 2709 4516 1254 add...
output:
1 2497 2497 2 827 2497 827 3 827 2497 4801 827 4 827 2497 2709 4801 827 5 827 2497 2709 4516 4801 827 4 656 827 2709 4801 827 5 656 827 2709 4773 4801 4773 6 827 1444 2497 2709 4516 4773 4773 7 827 1444 2338 2497 2709 4516 4773 4773 6 827 1254 1444 2709 4516 4773 4773 7 827 1254 1444 2709 4516 4773 ...
result:
ok n=8000, OK
Test #8:
score: -100
Wrong Answer
time: 158ms
memory: 76016kb
input:
8000 add 1866 1866 add 5228 5228 1866 add 4496 5228 4496 1866 add 2574 5228 4496 1866 2574 add 1492 5228 4496 1866 2574 1492 add 5427 5228 4496 1866 5427 add 3355 3355 5228 4496 1866 5427 add 5495 3355 5228 1866 5495 2574 1492 add 6421 3355 5228 1866 5495 2574 6421 1492 add 7543 3355 7543 5228 1866 ...
output:
1 1866 1866 2 1866 5228 5228 3 1866 4496 5228 5228 4 1866 2574 4496 5228 5228 5 1492 1866 2574 4496 5228 5228 4 1866 4496 5228 5427 5228 5 1866 3355 4496 5228 5427 3355 6 1492 1866 2574 3355 5228 5495 3355 7 1492 1866 2574 3355 5228 5495 6421 3355 6 1492 1866 3355 5228 5495 7543 3355 7 1492 1866 335...
result:
wrong answer WA after query 15979 found 261, answer is 4180