QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798172#1458. Binary Search AlgorithmKazemaruWA 158ms76016kbC++17990b2024-12-04 09:07:252024-12-04 09:07:27

Judging History

你现在查看的是最新测评结果

  • [2024-12-04 09:07:27]
  • 评测
  • 测评结果:WA
  • 用时:158ms
  • 内存:76016kb
  • [2024-12-04 09:07:25]
  • 提交

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