QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#32111#1458. Binary Search AlgorithmWu_RenAC ✓862ms3952kbC++111.8kb2022-05-17 15:16:482022-05-17 15:16:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 15:16:50]
  • 评测
  • 测评结果:AC
  • 用时:862ms
  • 内存:3952kb
  • [2022-05-17 15:16:48]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,tr[32010],rk[8010];
char s[10];
vector<int>v;
void qry(){
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	printf("%d ",v.size());
	for(int i:v) printf("%d ",i);puts("");
	fflush(stdout);
	for(int i=1,w;i<=v.size();i++) scanf("%d",&w),rk[w]=i;
}
void build(int l,int r,int t){
	tr[t]=-1;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,t<<1),build(mid+1,r,t<<1|1);
}
void add(int a,int l,int r,int t){
	if(tr[t]>0) v.push_back(tr[t]);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid) add(a,l,mid,t<<1);
	else add(a,mid+1,r,t<<1|1);
}
void upd_add(int a,int l,int r,int t){
	if(tr[t]<0||rk[tr[t]]>rk[a]) tr[t]=a;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid) upd_add(a,l,mid,t<<1);
	else upd_add(a,mid+1,r,t<<1|1);
}
void del(int a,int l,int r,int t){
	if(l==r) return;
	int mid=(l+r)>>1;
	if(a<=mid){
		del(a,l,mid,t<<1);
		if(tr[t<<1|1]>0) v.push_back(tr[t<<1|1]);
	}
	else{
		del(a,mid+1,r,t<<1|1);
		if(tr[t<<1]>0) v.push_back(tr[t<<1]);
	}
}
void upd_del(int a,int l,int r,int t){
	if(l==r){
		tr[t]=-1;
		return;
	}
	int mid=(l+r)>>1;
	if(a<=mid) upd_del(a,l,mid,t<<1);
	else upd_del(a,mid+1,r,t<<1|1);
	if(tr[t<<1]<0) tr[t]=tr[t<<1|1];
	else if(tr[t<<1|1]<0) tr[t]=tr[t<<1];
	else tr[t]=rk[tr[t<<1]]<rk[tr[t<<1|1]]?tr[t<<1]:tr[t<<1|1];
} 
void dfs(int l,int r,int t){
	if(l==r) return;
	int mid=(l+r)>>1;
	dfs(l,mid,t<<1),dfs(mid+1,r,t<<1|1);
}
int main(){
	scanf("%d",&n);
	build(1,n,1);
	for(int i=1,x;i<=2*n;i++){
		scanf("%s%d",s,&x);
		if(s[0]=='a'){
			v.clear();
			v.push_back(x);
			add(x,1,n,1);
			qry();
			upd_add(x,1,n,1);
		}
		else{
			v.clear();
			del(x,1,n,1);
			qry();
			upd_del(x,1,n,1);
		}
		dfs(1,n,1);
		printf("%d\n",tr[1]),fflush(stdout);
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 3812kb

input:

3
add 1
1
add 3
3 1
delete 1
3
add 2
3 2
delete 3
2
delete 2


output:

1 1 
1
2 1 3 
3
1 3 
3
2 2 3 
3
1 2 
2
0 
-1

result:

ok n=3, OK

Test #2:

score: 0
Accepted
time: 6ms
memory: 3736kb

input:

10
add 9
9
add 4
9 4
add 6
9 6
delete 9
4 6
add 7
7 4 6
delete 4
7
add 5
7 5
add 8
7 8
add 10
7 10
delete 8
7 10 5
add 3
3 7 5
add 2
3 2
delete 6
3 7 10
delete 10
3 7
delete 7
3
add 1
3 1 2
delete 1
3 5 2
delete 3
5 2
delete 5
2
delete 2


output:

1 9 
9
2 4 9 
9
2 6 9 
9
2 4 6 
4
3 4 6 7 
7
1 7 
7
2 5 7 
7
2 7 8 
7
2 7 10 
7
3 5 7 10 
7
3 3 5 7 
3
2 2 3 
3
3 3 7 10 
3
2 3 7 
3
1 3 
3
3 1 2 3 
3
3 2 3 5 
3
2 2 5 
5
1 2 
2
0 
-1

result:

ok n=10, OK

Test #3:

score: 0
Accepted
time: 39ms
memory: 3804kb

input:

100
add 81
81
add 96
81 96
add 94
81 94 96
add 32
81 32
add 35
81 32 35
add 59
81 59
add 50
81 50 32
add 57
81 57 59
add 39
39 81 50
add 55
39 81 57 55
add 23
39 23
add 40
39 40
add 5
39 23 5
add 2
39 23 5 2
delete 55
39 81 57 59
add 12
39 12 23 5
delete 40
39 81 50 12 32
add 51
39 81 57 51
add 65
3...

output:

1 81 
81
2 81 96 
81
3 81 94 96 
81
2 32 81 
81
3 32 35 81 
81
2 59 81 
81
3 32 50 81 
81
3 57 59 81 
81
3 39 50 81 
39
4 39 55 57 81 
39
2 23 39 
39
2 39 40 
39
3 5 23 39 
39
4 2 5 23 39 
39
4 39 57 59 81 
39
4 5 12 23 39 
39
5 12 32 39 50 81 
39
4 39 51 57 81 
39
4 39 57 65 81 
39
4 39 57 81 94 
3...

result:

ok n=100, OK

Test #4:

score: 0
Accepted
time: 18ms
memory: 3752kb

input:

100
add 71
71
add 75
71 75
add 43
43 71
add 69
43 71 69
add 55
43 71 55
add 89
43 71 89
add 31
43 31
add 52
43 71 55 52
add 24
24 43
add 6
24 6
add 9
24 6 9
add 62
24 71 62 55
add 19
24 19
add 35
24 43 35 31
add 38
24 43 35 38
add 39
39 24 43
add 63
39 71 63 62
add 68
39 68 71 69
add 98
39 68 89 98
...

output:

1 71 
71
2 71 75 
71
2 43 71 
43
3 43 69 71 
43
3 43 55 71 
43
3 43 71 89 
43
2 31 43 
43
4 43 52 55 71 
43
2 24 43 
24
2 6 24 
24
3 6 9 24 
24
4 24 55 62 71 
24
2 19 24 
24
4 24 31 35 43 
24
4 24 35 38 43 
24
3 24 39 43 
39
4 39 62 63 71 
39
4 39 68 69 71 
39
4 39 68 89 98 
39
3 39 43 44 
39
4 26 3...

result:

ok n=100, OK

Test #5:

score: 0
Accepted
time: 61ms
memory: 3788kb

input:

1000
add 93
93
add 917
93 917
add 921
93 917 921
add 70
93 70
add 949
93 949 917
add 777
93 949 777
add 237
93 237
add 581
581 93 949
add 461
581 93 461
add 319
581 93 319 461
add 42
581 93 42
add 690
581 690
add 631
581 631 690
add 135
581 93 237 135
add 424
581 93 319 424 461
add 647
581 631 647
a...

output:

1 93 
93
2 93 917 
93
3 93 917 921 
93
2 70 93 
93
3 93 917 949 
93
3 93 777 949 
93
2 93 237 
93
3 93 581 949 
581
3 93 461 581 
581
4 93 319 461 581 
581
3 42 93 581 
581
2 581 690 
581
3 581 631 690 
581
4 93 135 237 581 
581
5 93 319 424 461 581 
581
3 581 631 647 
581
5 93 135 165 237 581 
581
...

result:

ok n=1000, OK

Test #6:

score: 0
Accepted
time: 37ms
memory: 3788kb

input:

1000
add 589
589
add 844
589 844
add 341
589 341
add 362
589 341 362
add 955
955 589 844
add 565
955 589 565
add 467
955 341 467
add 664
955 589 664
add 167
167 955 341
add 879
167 955 879
add 934
167 934 955 879
add 757
167 934 757 844
add 941
167 934 955 941
add 56
167 56
add 337
167 337 341
add 8...

output:

1 589 
589
2 589 844 
589
2 341 589 
589
3 341 362 589 
589
3 589 844 955 
955
3 565 589 955 
955
3 341 467 955 
955
3 589 664 955 
955
3 167 341 955 
167
3 167 879 955 
167
4 167 879 934 955 
167
4 167 757 844 934 
167
4 167 934 941 955 
167
2 56 167 
167
3 167 337 341 
167
4 167 879 880 934 
167
4...

result:

ok n=1000, OK

Test #7:

score: 0
Accepted
time: 631ms
memory: 3860kb

input:

8000
add 2497
2497
add 827
827 2497
add 4801
827 4801
add 2709
827 2709 2497
add 4516
827 4801 4516
add 656
827 656
add 4773
4773 827 4801
add 1444
4773 827 1444
add 2338
4773 827 2709 2338 2497
add 1254
4773 827 1444 1254
add 5749
4773 5749
add 3926
4773 827 3926 2709
add 7537
4773 7537
add 6800
47...

output:

1 2497 
2497
2 827 2497 
827
2 827 4801 
827
3 827 2497 2709 
827
3 827 4516 4801 
827
2 656 827 
827
3 827 4773 4801 
4773
3 827 1444 4773 
4773
5 827 2338 2497 2709 4773 
4773
4 827 1254 1444 4773 
4773
2 4773 5749 
4773
4 827 2709 3926 4773 
4773
2 4773 7537 
4773
3 4773 6800 7537 
4773
3 5 827 4...

result:

ok n=8000, OK

Test #8:

score: 0
Accepted
time: 683ms
memory: 3896kb

input:

8000
add 1866
1866
add 5228
5228 1866
add 4496
5228 4496
add 2574
5228 1866 2574
add 1492
5228 1866 1492
add 5427
5228 5427
add 3355
3355 5228 1866 2574
add 5495
3355 5228 5495 5427
add 6421
3355 5228 6421
add 7543
3355 7543 5228 6421
add 4400
3355 4400 7543 5228 4496
add 4311
3355 4400 4311
add 757...

output:

1 1866 
1866
2 1866 5228 
5228
2 4496 5228 
5228
3 1866 2574 5228 
5228
3 1492 1866 5228 
5228
2 5228 5427 
5228
4 1866 2574 3355 5228 
3355
4 3355 5228 5427 5495 
3355
3 3355 5228 6421 
3355
4 3355 5228 6421 7543 
3355
5 3355 4400 4496 5228 7543 
3355
3 3355 4311 4400 
3355
4 3355 4400 7543 7572 
7...

result:

ok n=8000, OK

Test #9:

score: 0
Accepted
time: 28ms
memory: 3672kb

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 129
add 345
964 129 345
add 454
964 129 345 454
add 614
964 650 614
add 11
964 129 11
add 963
964 963
add 357
964 129 345 357
add 300
964 129 345 300
add 785
964 785
add 700
964 650 700
add 442
964 129 345 454 442
add 14
964 129 11 14
add ...

output:

1 964 
964
2 650 964 
964
2 964 967 
964
2 129 964 
964
3 129 345 964 
964
4 129 345 454 964 
964
3 614 650 964 
964
3 11 129 964 
964
2 963 964 
964
4 129 345 357 964 
964
4 129 300 345 964 
964
2 785 964 
964
3 650 700 964 
964
5 129 345 442 454 964 
964
4 11 14 129 964 
964
4 11 79 129 964 
964
4...

result:

ok n=1000, OK

Test #10:

score: 0
Accepted
time: 58ms
memory: 3784kb

input:

1000
add 651
651
add 792
792 651
add 816
792 816
add 325
792 325
add 876
792 876
add 408
792 408 325
add 289
792 289 408 325
add 746
792 746 651
add 492
792 289 408 492
add 2
792 289 2
add 462
792 462 289 408 492
add 98
792 462 98 2
add 68
792 462 68 98
add 69
792 462 68 69
add 834
792 816 834
add 6...

output:

1 651 
651
2 651 792 
792
2 792 816 
792
2 325 792 
792
2 792 876 
792
3 325 408 792 
792
4 289 325 408 792 
792
3 651 746 792 
792
4 289 408 492 792 
792
3 2 289 792 
792
5 289 408 462 492 792 
792
4 2 98 462 792 
792
4 68 98 462 792 
792
4 68 69 462 792 
792
3 792 816 834 
792
4 651 664 746 792 
7...

result:

ok n=1000, OK

Test #11:

score: 0
Accepted
time: 648ms
memory: 3860kb

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 650 129
add 3768
4964 650 3768
add 1551
4964 650 1551
add 6223
4964 6871 6223
add 3875
4964 650 3768 3875
add 6536
4964 6871 6536
add 6438
4964 6871 6223 6438
add 5015
4964 5015
add 2528
4964 650 3768 2528
add 1952
4964 650 1551 195...

output:

1 4964 
4964
2 650 4964 
4964
2 4964 6871 
4964
3 129 650 4964 
4964
3 650 3768 4964 
4964
3 650 1551 4964 
4964
3 4964 6223 6871 
4964
4 650 3768 3875 4964 
4964
3 4964 6536 6871 
4964
4 4964 6223 6438 6871 
4964
2 4964 5015 
4964
4 650 2528 3768 4964 
4964
4 650 1551 1952 4964 
4964
5 4964 6223 64...

result:

ok n=8000, OK

Test #12:

score: 0
Accepted
time: 723ms
memory: 3860kb

input:

8000
add 3562
3562
add 2628
3562 2628
add 6508
6508 3562
add 1830
6508 3562 1830
add 6995
6508 6995
add 2741
6508 2741 3562 2628
add 3523
6508 2741 3562 3523
add 4497
6508 4497
add 1175
6508 2741 1175 1830
add 5626
6508 4497 5626
add 2252
6508 2741 2252
add 2606
6508 2741 2606
add 6190
6508 6190
add...

output:

1 3562 
3562
2 2628 3562 
3562
2 3562 6508 
6508
3 1830 3562 6508 
6508
2 6508 6995 
6508
4 2628 2741 3562 6508 
6508
4 2741 3523 3562 6508 
6508
2 4497 6508 
6508
4 1175 1830 2741 6508 
6508
3 4497 5626 6508 
6508
3 2252 2741 6508 
6508
3 2606 2741 6508 
6508
2 6190 6508 
6508
4 15 1175 2741 6508 
...

result:

ok n=8000, OK

Test #13:

score: 0
Accepted
time: 3ms
memory: 3860kb

input:

10
add 3
3
add 7
3 7
add 10
3 7 10
add 1
3 1
add 9
3 7 10 9
add 5
3 5
add 4
3 5 4
add 8
3 7 8
add 6
3 7 6
add 2
3 1 2
delete 3
7 1 5
delete 7
10 1 8 6
delete 1
10 5 2
delete 10
9 5 8
delete 5
9 4 2
delete 9
4 8
delete 8
4 6
delete 4
6 2
delete 6
2
delete 2


output:

1 3 
3
2 3 7 
3
3 3 7 10 
3
2 1 3 
3
4 3 7 9 10 
3
2 3 5 
3
3 3 4 5 
3
3 3 7 8 
3
3 3 6 7 
3
3 1 2 3 
3
3 1 5 7 
7
4 1 6 8 10 
10
3 2 5 10 
10
3 5 8 9 
9
3 2 4 9 
9
2 4 8 
4
2 4 6 
4
2 2 6 
6
1 2 
2
0 
-1

result:

ok n=10, OK

Test #14:

score: 0
Accepted
time: 6ms
memory: 3700kb

input:

10
add 9
9
add 5
9 5
add 2
9 5 2
add 7
7 9
add 4
7 5 4
add 3
3 7 5 2
add 1
3 1 2
add 6
3 7 6
add 10
3 7 10 9
add 8
3 7 8
delete 7
3 10 8 6
delete 3
10 1 5
delete 9
10 1 8
delete 5
10 1 4
delete 10
1 8
delete 1
4 8 2
delete 8
4 6
delete 4
6 2
delete 2
6
delete 6


output:

1 9 
9
2 5 9 
9
3 2 5 9 
9
2 7 9 
7
3 4 5 7 
7
4 2 3 5 7 
3
3 1 2 3 
3
3 3 6 7 
3
4 3 7 9 10 
3
3 3 7 8 
3
4 3 6 8 10 
3
3 1 5 10 
10
3 1 8 10 
10
3 1 4 10 
10
2 1 8 
1
3 2 4 8 
4
2 4 6 
4
2 2 6 
6
1 6 
6
0 
-1

result:

ok n=10, OK

Test #15:

score: 0
Accepted
time: 30ms
memory: 3740kb

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 129
add 345
964 129 345
add 454
964 129 345 454
add 614
964 650 614
add 11
964 129 11
add 963
964 963
add 357
964 129 345 357
add 300
964 129 345 300
add 785
964 785
add 700
964 650 700
add 442
964 129 345 454 442
add 14
964 129 11 14
add ...

output:

1 964 
964
2 650 964 
964
2 964 967 
964
2 129 964 
964
3 129 345 964 
964
4 129 345 454 964 
964
3 614 650 964 
964
3 11 129 964 
964
2 963 964 
964
4 129 345 357 964 
964
4 129 300 345 964 
964
2 785 964 
964
3 650 700 964 
964
5 129 345 442 454 964 
964
4 11 14 129 964 
964
4 11 79 129 964 
964
4...

result:

ok n=1000, OK

Test #16:

score: 0
Accepted
time: 32ms
memory: 3816kb

input:

1000
add 871
871
add 449
449 871
add 644
644 449 871
add 97
97 644 449
add 853
853 97 644 871
add 496
496 853 97 449
add 418
418 496
add 207
207 418 97
add 401
401 207 418
add 519
519 401 853 644
add 276
276 519 401
add 576
576 276 519
add 74
74 576 276 207 97
add 194
194 74 207
add 719
719 194 576 ...

output:

1 871 
871
2 449 871 
449
3 449 644 871 
644
3 97 449 644 
97
4 97 644 853 871 
853
4 97 449 496 853 
496
2 418 496 
418
3 97 207 418 
207
3 207 401 418 
401
4 401 519 644 853 
519
3 276 401 519 
276
3 276 519 576 
576
5 74 97 207 276 576 
74
3 74 194 207 
194
4 194 576 644 719 
719
4 194 252 276 71...

result:

ok n=1000, OK

Test #17:

score: 0
Accepted
time: 18ms
memory: 3712kb

input:

1000
add 35
35
add 747
35 747
add 391
35 391
add 770
35 770 747
add 707
35 770 747 707
add 344
35 391 344
add 881
35 770 881
add 753
35 770 753
add 266
35 391 266 344
add 126
126 35
add 11
11 126 35
add 705
11 770 747 707 705
add 672
11 770 747 672
add 107
11 107
add 439
11 391 439
add 958
11 770 95...

output:

1 35 
35
2 35 747 
35
2 35 391 
35
3 35 747 770 
35
4 35 707 747 770 
35
3 35 344 391 
35
3 35 770 881 
35
3 35 753 770 
35
4 35 266 344 391 
35
2 35 126 
126
3 11 35 126 
11
5 11 705 707 747 770 
11
4 11 672 747 770 
11
2 11 107 
11
3 11 391 439 
11
4 11 770 881 958 
11
3 11 391 432 
11
2 11 26 
11...

result:

ok n=1000, OK

Test #18:

score: 0
Accepted
time: 49ms
memory: 3800kb

input:

1000
add 914
914
add 326
326 914
add 650
650 326 914
add 629
650 629
add 626
650 626 629
add 416
650 416 326
add 785
650 785 914
add 837
650 785 837
add 300
650 300 416 326
add 700
650 700
add 164
650 300 164
add 786
650 785 786
add 304
650 300 304
add 450
650 300 450 416
add 72
650 300 72 164
add 3...

output:

1 914 
914
2 326 914 
326
3 326 650 914 
650
2 629 650 
650
3 626 629 650 
650
3 326 416 650 
650
3 650 785 914 
650
3 650 785 837 
650
4 300 326 416 650 
650
2 650 700 
650
3 164 300 650 
650
3 650 785 786 
650
3 300 304 650 
650
4 300 416 450 650 
650
4 72 164 300 650 
650
4 300 326 357 650 
650
4...

result:

ok n=1000, OK

Test #19:

score: 0
Accepted
time: 28ms
memory: 3836kb

input:

1000
add 129
129
add 786
129 786
add 614
129 614 786
add 967
967 129 614 786
add 454
967 129 454
add 34
967 129 34
add 700
967 614 700
add 300
967 129 454 300
add 488
967 129 454 488
add 963
967 963
add 79
967 129 79 34
add 743
967 614 700 743
add 11
967 129 11 79 34
add 384
967 129 454 384
add 980
...

output:

1 129 
129
2 129 786 
129
3 129 614 786 
129
4 129 614 786 967 
967
3 129 454 967 
967
3 34 129 967 
967
3 614 700 967 
967
4 129 300 454 967 
967
4 129 454 488 967 
967
2 963 967 
967
4 34 79 129 967 
967
4 614 700 743 967 
967
5 11 34 79 129 967 
967
4 129 384 454 967 
967
2 967 980 
967
3 967 972...

result:

ok n=1000, OK

Test #20:

score: 0
Accepted
time: 791ms
memory: 3888kb

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 650 129
add 3768
4964 650 3768
add 1551
4964 650 1551
add 6223
4964 6871 6223
add 3875
4964 650 3768 3875
add 6536
4964 6871 6536
add 6438
4964 6871 6223 6438
add 5015
4964 5015
add 2528
4964 650 3768 2528
add 1952
4964 650 1551 195...

output:

1 4964 
4964
2 650 4964 
4964
2 4964 6871 
4964
3 129 650 4964 
4964
3 650 3768 4964 
4964
3 650 1551 4964 
4964
3 4964 6223 6871 
4964
4 650 3768 3875 4964 
4964
3 4964 6536 6871 
4964
4 4964 6223 6438 6871 
4964
2 4964 5015 
4964
4 650 2528 3768 4964 
4964
4 650 1551 1952 4964 
4964
5 4964 6223 64...

result:

ok n=8000, OK

Test #21:

score: 0
Accepted
time: 671ms
memory: 3792kb

input:

8000
add 3493
3493
add 5110
5110 3493
add 533
533 5110 3493
add 1700
1700 533
add 4277
4277 1700 5110
add 2368
2368 4277 1700 3493
add 4495
4495 2368 4277
add 4305
4305 4495 4277
add 6965
6965 4305
add 2503
2503 6965 2368
add 4339
4339 2503 6965 4305
add 5195
5195 4339 5110
add 2364
2364 5195 2503 2...

output:

1 3493 
3493
2 3493 5110 
5110
3 533 3493 5110 
533
2 533 1700 
1700
3 1700 4277 5110 
4277
4 1700 2368 3493 4277 
2368
3 2368 4277 4495 
4495
3 4277 4305 4495 
4305
2 4305 6965 
6965
3 2368 2503 6965 
2503
4 2503 4305 4339 6965 
4339
3 4339 5110 5195 
5195
4 2364 2368 2503 5195 
2364
3 2364 3493 38...

result:

ok n=8000, OK

Test #22:

score: 0
Accepted
time: 622ms
memory: 3864kb

input:

8000
add 612
612
add 2743
612 2743
add 7916
612 7916
add 1433
1433 612
add 2140
1433 2140 2743
add 840
1433 612 840
add 4289
1433 4289 7916
add 3912
1433 2140 3912
add 6323
1433 4289 6323 7916
add 3859
1433 3859 2140 3912
add 4368
1433 4289 4368
add 6046
1433 4289 6046 6323
add 1405
1433 1405
add 56...

output:

1 612 
612
2 612 2743 
612
2 612 7916 
612
2 612 1433 
1433
3 1433 2140 2743 
1433
3 612 840 1433 
1433
3 1433 4289 7916 
1433
3 1433 2140 3912 
1433
4 1433 4289 6323 7916 
1433
4 1433 2140 3859 3912 
1433
3 1433 4289 4368 
1433
4 1433 4289 6046 6323 
1433
2 1405 1433 
1433
3 1433 4289 5687 
1433
5 ...

result:

ok n=8000, OK

Test #23:

score: 0
Accepted
time: 862ms
memory: 3860kb

input:

8000
add 3393
3393
add 5029
5029 3393
add 650
650 5029 3393
add 3599
650 3393 3599
add 5102
650 5102 5029
add 5122
650 5102 5122
add 6641
650 5102 6641
add 475
650 475
add 1323
650 1323
add 1821
650 1821 1323
add 3447
650 3393 3447
add 578
650 578
add 7293
650 5102 7293 6641
add 5600
650 5102 5600
a...

output:

1 3393 
3393
2 3393 5029 
5029
3 650 3393 5029 
650
3 650 3393 3599 
650
3 650 5029 5102 
650
3 650 5102 5122 
650
3 650 5102 6641 
650
2 475 650 
650
2 650 1323 
650
3 650 1323 1821 
650
3 650 3393 3447 
650
2 578 650 
650
4 650 5102 6641 7293 
650
3 650 5102 5600 
650
4 650 5102 5600 5900 
650
3 6...

result:

ok n=8000, OK

Test #24:

score: 0
Accepted
time: 688ms
memory: 3884kb

input:

8000
add 3768
3768
add 878
3768 878
add 5029
3768 5029
add 1821
3768 1821 878
add 5001
3768 5029 5001
add 1608
3768 1821 1608
add 2691
3768 2691
add 7293
3768 5029 7293
add 7275
3768 5029 7275 7293
add 6223
3768 6223 5029 7275
add 227
3768 1821 878 227
add 3809
3768 3809
add 4675
3768 6223 4675 5029...

output:

1 3768 
3768
2 878 3768 
3768
2 3768 5029 
3768
3 878 1821 3768 
3768
3 3768 5001 5029 
3768
3 1608 1821 3768 
3768
2 2691 3768 
3768
3 3768 5029 7293 
3768
4 3768 5029 7275 7293 
3768
4 3768 5029 6223 7275 
3768
4 227 878 1821 3768 
3768
2 3768 3809 
3768
4 3768 4675 5029 6223 
3768
5 3768 4675 502...

result:

ok n=8000, OK

Test #25:

score: 0
Accepted
time: 5ms
memory: 3800kb

input:

10
add 3
3
add 7
3 7
add 10
3 7 10
add 1
3 1
add 9
3 7 10 9
add 5
3 5
add 4
3 5 4
add 8
3 7 8
add 6
3 7 6
add 2
3 1 2
delete 3
7 1 5
delete 7
10 1 8 6
delete 1
10 5 2
delete 10
9 5 8
delete 5
9 4 2
delete 9
4 8
delete 4
8 2
delete 8
6 2
delete 6
2
delete 2


output:

1 3 
3
2 3 7 
3
3 3 7 10 
3
2 1 3 
3
4 3 7 9 10 
3
2 3 5 
3
3 3 4 5 
3
3 3 7 8 
3
3 3 6 7 
3
3 1 2 3 
3
3 1 5 7 
7
4 1 6 8 10 
10
3 2 5 10 
10
3 5 8 9 
9
3 2 4 9 
9
2 4 8 
4
2 2 8 
8
2 2 6 
6
1 2 
2
0 
-1

result:

ok n=10, OK

Test #26:

score: 0
Accepted
time: 7ms
memory: 3748kb

input:

10
add 10
10
add 8
10 8
add 4
10 4
add 3
3 10 4
add 6
3 10 8 6
add 1
3 1
add 7
3 7 10 8 6
add 2
3 1 2
add 9
3 7 10 9
add 5
3 5 4
delete 3
7 1 5
delete 10
7 1 9
delete 7
1 9 8 6
delete 1
9 5 2
delete 9
5 8
delete 8
5 6
delete 5
4 6 2
delete 4
6 2
delete 6
2
delete 2


output:

1 10 
10
2 8 10 
10
2 4 10 
10
3 3 4 10 
3
4 3 6 8 10 
3
2 1 3 
3
5 3 6 7 8 10 
3
3 1 2 3 
3
4 3 7 9 10 
3
3 3 4 5 
3
3 1 5 7 
7
3 1 7 9 
7
4 1 6 8 9 
1
3 2 5 9 
9
2 5 8 
5
2 5 6 
5
3 2 4 6 
4
2 2 6 
6
1 2 
2
0 
-1

result:

ok n=10, OK

Test #27:

score: 0
Accepted
time: 52ms
memory: 3760kb

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 129
add 345
964 129 345
add 454
964 129 345 454
add 614
964 650 614
add 11
964 129 11
add 963
964 963
add 357
964 129 345 357
add 300
964 129 345 300
add 785
964 785
add 700
964 650 700
add 442
964 129 345 454 442
add 14
964 129 11 14
add ...

output:

1 964 
964
2 650 964 
964
2 964 967 
964
2 129 964 
964
3 129 345 964 
964
4 129 345 454 964 
964
3 614 650 964 
964
3 11 129 964 
964
2 963 964 
964
4 129 345 357 964 
964
4 129 300 345 964 
964
2 785 964 
964
3 650 700 964 
964
5 129 345 442 454 964 
964
4 11 14 129 964 
964
4 11 79 129 964 
964
4...

result:

ok n=1000, OK

Test #28:

score: 0
Accepted
time: 55ms
memory: 3872kb

input:

1000
add 871
871
add 449
449 871
add 644
644 449 871
add 97
97 644 449
add 853
853 97 644 871
add 496
496 853 97 449
add 418
418 496
add 207
207 418 97
add 401
401 207 418
add 519
519 401 853 644
add 276
276 519 401
add 576
576 276 519
add 74
74 576 276 207 97
add 194
194 74 207
add 719
719 194 576 ...

output:

1 871 
871
2 449 871 
449
3 449 644 871 
644
3 97 449 644 
97
4 97 644 853 871 
853
4 97 449 496 853 
496
2 418 496 
418
3 97 207 418 
207
3 207 401 418 
401
4 401 519 644 853 
519
3 276 401 519 
276
3 276 519 576 
576
5 74 97 207 276 576 
74
3 74 194 207 
194
4 194 576 644 719 
719
4 194 252 276 71...

result:

ok n=1000, OK

Test #29:

score: 0
Accepted
time: 36ms
memory: 3824kb

input:

1000
add 986
986
add 800
986 800
add 897
986 897
add 601
601 986
add 858
858 601 986 800
add 627
858 601 627
add 398
858 398
add 124
858 124 398
add 885
858 885 986 897
add 554
858 554 601
add 234
858 124 234
add 482
858 124 482 398
add 489
858 124 482 489
add 771
858 800 771
add 508
858 554 508
add...

output:

1 986 
986
2 800 986 
986
2 897 986 
986
2 601 986 
601
4 601 800 858 986 
858
3 601 627 858 
858
2 398 858 
858
3 124 398 858 
858
4 858 885 897 986 
858
3 554 601 858 
858
3 124 234 858 
858
4 124 398 482 858 
858
4 124 482 489 858 
858
3 771 800 858 
858
3 508 554 858 
858
4 554 627 748 858 
858
...

result:

ok n=1000, OK

Test #30:

score: 0
Accepted
time: 62ms
memory: 3820kb

input:

1000
add 101
101
add 442
442 101
add 183
442 101 183
add 373
442 373
add 837
442 837
add 326
442 373 326
add 585
442 585 837
add 450
442 450
add 15
442 101 15
add 626
442 585 626
add 914
442 585 837 914
add 786
442 585 786 837
add 494
442 494
add 828
442 585 828 786 837
add 93
442 101 93
add 878
442...

output:

1 101 
101
2 101 442 
442
3 101 183 442 
442
2 373 442 
442
2 442 837 
442
3 326 373 442 
442
3 442 585 837 
442
2 442 450 
442
3 15 101 442 
442
3 442 585 626 
442
4 442 585 837 914 
442
4 442 585 786 837 
442
2 442 494 
442
5 442 585 786 828 837 
442
3 93 101 442 
442
5 442 585 828 878 914 
442
3 ...

result:

ok n=1000, OK

Test #31:

score: 0
Accepted
time: 69ms
memory: 3740kb

input:

1000
add 79
79
add 442
442 79
add 454
454 442
add 520
454 520
add 101
454 79 101
add 343
454 343
add 585
454 585 520
add 700
454 700 585
add 632
454 700 632
add 300
454 300 343
add 878
454 700 878
add 64
454 79 64
add 227
454 79 227
add 964
964 454 700 878
add 828
964 828
add 488
964 454 488
add 980...

output:

1 79 
79
2 79 442 
442
2 442 454 
454
2 454 520 
454
3 79 101 454 
454
2 343 454 
454
3 454 520 585 
454
3 454 585 700 
454
3 454 632 700 
454
3 300 343 454 
454
3 454 700 878 
454
3 64 79 454 
454
3 79 227 454 
454
4 454 700 878 964 
964
2 828 964 
964
3 454 488 964 
964
2 964 980 
964
4 581 585 70...

result:

ok n=1000, OK

Test #32:

score: 0
Accepted
time: 38ms
memory: 3672kb

input:

1000
add 964
964
add 871
964 871
add 449
964 449
add 644
964 644
add 97
964 97 449
add 853
964 853 871
add 496
964 496 97 449
add 418
964 418 496
add 207
964 207 418 97
add 401
964 401 207 418
add 519
964 519 644
add 276
964 276 401
add 576
964 576 519
add 74
964 74 276 207 97
add 194
964 194 74 207...

output:

1 964 
964
2 871 964 
964
2 449 964 
964
2 644 964 
964
3 97 449 964 
964
3 853 871 964 
964
4 97 449 496 964 
964
3 418 496 964 
964
4 97 207 418 964 
964
4 207 401 418 964 
964
3 519 644 964 
964
3 276 401 964 
964
3 519 576 964 
964
5 74 97 207 276 964 
964
4 74 194 207 964 
964
4 576 644 719 964...

result:

ok n=1000, OK

Test #33:

score: 0
Accepted
time: 809ms
memory: 3892kb

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 650 129
add 3768
4964 650 3768
add 1551
4964 650 1551
add 6223
4964 6871 6223
add 3875
4964 650 3768 3875
add 6536
4964 6871 6536
add 6438
4964 6871 6223 6438
add 5015
4964 5015
add 2528
4964 650 3768 2528
add 1952
4964 650 1551 195...

output:

1 4964 
4964
2 650 4964 
4964
2 4964 6871 
4964
3 129 650 4964 
4964
3 650 3768 4964 
4964
3 650 1551 4964 
4964
3 4964 6223 6871 
4964
4 650 3768 3875 4964 
4964
3 4964 6536 6871 
4964
4 4964 6223 6438 6871 
4964
2 4964 5015 
4964
4 650 2528 3768 4964 
4964
4 650 1551 1952 4964 
4964
5 4964 6223 64...

result:

ok n=8000, OK

Test #34:

score: 0
Accepted
time: 744ms
memory: 3860kb

input:

8000
add 3493
3493
add 5110
5110 3493
add 533
533 5110 3493
add 1700
1700 533
add 4277
4277 1700 5110
add 2368
2368 4277 1700 3493
add 4495
4495 2368 4277
add 4305
4305 4495 4277
add 6965
6965 4305
add 2503
2503 6965 2368
add 4339
4339 2503 6965 4305
add 5195
5195 4339 5110
add 2364
2364 5195 2503 2...

output:

1 3493 
3493
2 3493 5110 
5110
3 533 3493 5110 
533
2 533 1700 
1700
3 1700 4277 5110 
4277
4 1700 2368 3493 4277 
2368
3 2368 4277 4495 
4495
3 4277 4305 4495 
4305
2 4305 6965 
6965
3 2368 2503 6965 
2503
4 2503 4305 4339 6965 
4339
3 4339 5110 5195 
5195
4 2364 2368 2503 5195 
2364
3 2364 3493 38...

result:

ok n=8000, OK

Test #35:

score: 0
Accepted
time: 632ms
memory: 3864kb

input:

8000
add 1338
1338
add 1220
1338 1220
add 2046
1338 2046
add 5158
5158 1338
add 1439
5158 1338 1439
add 412
5158 1338 412
add 5737
5737 5158
add 3968
5737 1338 2046 3968
add 703
5737 1338 703 412
add 2858
5737 2858 1338 2046
add 2783
5737 2858 2783
add 3798
5737 2858 3798 3968
add 5455
5737 5158 545...

output:

1 1338 
1338
2 1220 1338 
1338
2 1338 2046 
1338
2 1338 5158 
5158
3 1338 1439 5158 
5158
3 412 1338 5158 
5158
2 5158 5737 
5737
4 1338 2046 3968 5737 
5737
4 412 703 1338 5737 
5737
4 1338 2046 2858 5737 
5737
3 2783 2858 5737 
5737
4 2858 3798 3968 5737 
5737
3 5158 5455 5737 
5737
5 2858 3798 38...

result:

ok n=8000, OK

Test #36:

score: 0
Accepted
time: 707ms
memory: 3880kb

input:

8000
add 6131
6131
add 4520
6131 4520
add 6799
6131 6799
add 1676
6131 1676
add 1844
6131 1676 1844
add 6912
6131 6912 6799
add 3621
6131 3621 1676
add 4018
4018 6131 4520
add 1178
4018 1178 3621 1676
add 2082
4018 1178 3621 2082
add 6172
6172 4018 6131
add 1568
6172 1178 1568 1676
add 7404
6172 740...

output:

1 6131 
6131
2 4520 6131 
6131
2 6131 6799 
6131
2 1676 6131 
6131
3 1676 1844 6131 
6131
3 6131 6799 6912 
6131
3 1676 3621 6131 
6131
3 4018 4520 6131 
4018
4 1178 1676 3621 4018 
4018
4 1178 2082 3621 4018 
4018
3 4018 6131 6172 
6172
4 1178 1568 1676 6172 
6172
2 6172 7404 
6172
4 1178 3621 3759...

result:

ok n=8000, OK

Test #37:

score: 0
Accepted
time: 646ms
memory: 3900kb

input:

8000
add 893
893
add 2960
2960 893
add 7459
7459 2960
add 111
111 7459 2960 893
add 1185
111 1185
add 3327
111 3327 2960
add 5397
5397 111 7459
add 3963
5397 111 3327 3963
add 4988
5397 4988
add 6640
5397 7459 6640
add 3584
5397 111 3327 3584 3963
add 5536
5397 5536
add 6178
5397 7459 6640 6178
add ...

output:

1 893 
893
2 893 2960 
2960
2 2960 7459 
7459
4 111 893 2960 7459 
111
2 111 1185 
111
3 111 2960 3327 
111
3 111 5397 7459 
5397
4 111 3327 3963 5397 
5397
2 4988 5397 
5397
3 5397 6640 7459 
5397
5 111 3327 3584 3963 5397 
5397
2 5397 5536 
5397
4 5397 6178 6640 7459 
5397
4 111 1119 1185 5397 
53...

result:

ok n=8000, OK

Test #38:

score: 0
Accepted
time: 783ms
memory: 3948kb

input:

8000
add 3768
3768
add 355
3768 355
add 5755
3768 5755
add 5029
3768 5029 5755
add 5530
3768 5029 5755 5530
add 7826
3768 5029 7826
add 6194
3768 5029 6194 7826
add 1821
3768 1821 355
add 1113
3768 1821 1113
add 5015
3768 5015 5029
add 343
3768 1821 343 355
add 650
650 3768 1821 343
add 878
650 878
...

output:

1 3768 
3768
2 355 3768 
3768
2 3768 5755 
3768
3 3768 5029 5755 
3768
4 3768 5029 5530 5755 
3768
3 3768 5029 7826 
3768
4 3768 5029 6194 7826 
3768
3 355 1821 3768 
3768
3 1113 1821 3768 
3768
3 3768 5015 5029 
3768
4 343 355 1821 3768 
3768
4 343 650 1821 3768 
650
2 650 878 
650
4 650 5015 6194 ...

result:

ok n=8000, OK

Test #39:

score: 0
Accepted
time: 645ms
memory: 3884kb

input:

8000
add 3325
3325
add 5911
3325 5911
add 664
3325 664
add 708
3325 708 664
add 3589
3325 3589
add 3869
3325 3869 3589
add 6353
3325 6353 5911
add 5408
3325 6353 5408 5911
add 2396
3325 2396
add 1926
3325 1926 708
add 3822
3325 3869 3822
add 2476
3325 2476 2396
add 6482
3325 6353 6482
add 6067
3325 ...

output:

1 3325 
3325
2 3325 5911 
3325
2 664 3325 
3325
3 664 708 3325 
3325
2 3325 3589 
3325
3 3325 3589 3869 
3325
3 3325 5911 6353 
3325
4 3325 5408 5911 6353 
3325
2 2396 3325 
3325
3 708 1926 3325 
3325
3 3325 3822 3869 
3325
3 2396 2476 3325 
3325
3 3325 6353 6482 
3325
3 3325 6067 6353 
3325
3 3325 ...

result:

ok n=8000, OK

Test #40:

score: 0
Accepted
time: 666ms
memory: 3952kb

input:

8000
add 520
520
add 4857
4857 520
add 3380
4857 520 3380
add 5397
4857 5397
add 1551
1551 4857 520
add 4675
1551 4857 4675
add 5755
1551 4857 5755 5397
add 2691
1551 3380 2691
add 3809
1551 3809 3380
add 1608
1551 1608
add 4679
1551 4857 4675 4679
add 6194
1551 4857 6194
add 6223
1551 6223 4857 619...

output:

1 520 
520
2 520 4857 
4857
3 520 3380 4857 
4857
2 4857 5397 
4857
3 520 1551 4857 
1551
3 1551 4675 4857 
1551
4 1551 4857 5397 5755 
1551
3 1551 2691 3380 
1551
3 1551 3380 3809 
1551
2 1551 1608 
1551
4 1551 4675 4679 4857 
1551
3 1551 4857 6194 
1551
4 1551 4857 6194 6223 
1551
6 1551 4857 5029...

result:

ok n=8000, OK

Test #41:

score: 0
Accepted
time: 749ms
memory: 3868kb

input:

8000
add 3540
3540
add 6114
6114 3540
add 7095
6114 7095
add 7142
6114 7095 7142
add 4694
6114 4694
add 1040
6114 3540 1040
add 2503
6114 3540 2503
add 5498
6114 4694 5498
add 4061
6114 4061 4694
add 213
6114 3540 1040 213
add 300
6114 300 3540 1040 213
add 20
6114 300 20 213
add 2632
2632 6114 300 ...

output:

1 3540 
3540
2 3540 6114 
6114
2 6114 7095 
6114
3 6114 7095 7142 
6114
2 4694 6114 
6114
3 1040 3540 6114 
6114
3 2503 3540 6114 
6114
3 4694 5498 6114 
6114
3 4061 4694 6114 
6114
4 213 1040 3540 6114 
6114
5 213 300 1040 3540 6114 
6114
4 20 213 300 6114 
6114
5 300 2503 2632 3540 6114 
2632
4 30...

result:

ok n=8000, OK

Test #42:

score: 0
Accepted
time: 661ms
memory: 3816kb

input:

8000
add 6663
6663
add 7408
7408 6663
add 2088
2088 7408
add 1213
2088 1213
add 3752
3752 2088
add 4898
3752 7408 4898
add 6916
3752 7408 6916 6663
add 3470
3470 3752
add 6588
3470 6588 7408 6916 6663
add 6136
3470 6588 6136
add 3508
3508 3470 3752
add 3236
3508 3470 3236
add 5297
3508 6588 4898 529...

output:

1 6663 
6663
2 6663 7408 
7408
2 2088 7408 
2088
2 1213 2088 
2088
2 2088 3752 
3752
3 3752 4898 7408 
3752
4 3752 6663 6916 7408 
3752
2 3470 3752 
3470
5 3470 6588 6663 6916 7408 
3470
3 3470 6136 6588 
3470
3 3470 3508 3752 
3508
3 3236 3470 3508 
3508
4 3508 4898 5297 6588 
3508
4 3508 4892 4898...

result:

ok n=8000, OK

Test #43:

score: 0
Accepted
time: 680ms
memory: 3912kb

input:

8000
add 6663
6663
add 2364
6663 2364
add 7626
6663 7626
add 131
131 6663 2364
add 6567
131 6567 6663
add 6812
131 6567 6812
add 4718
131 6567 4718
add 1312
1312 131
add 5091
1312 5091 6567 4718
add 4819
4819 1312 5091 4718
add 1421
4819 1312 1421
add 2361
4819 1312 2361 2364
add 3596
4819 1312 3596...

output:

1 6663 
6663
2 2364 6663 
6663
2 6663 7626 
6663
3 131 2364 6663 
131
3 131 6567 6663 
131
3 131 6567 6812 
131
3 131 4718 6567 
131
2 131 1312 
1312
4 1312 4718 5091 6567 
1312
4 1312 4718 4819 5091 
4819
3 1312 1421 4819 
4819
4 1312 2361 2364 4819 
4819
4 1312 2361 3596 4819 
4819
4 4819 6567 681...

result:

ok n=8000, OK

Test #44:

score: 0
Accepted
time: 670ms
memory: 3888kb

input:

8000
add 4339
4339
add 615
615 4339
add 7105
615 7105 4339
add 4718
615 7105 4718 4339
add 2503
615 2503
add 4810
615 7105 4810 4718
add 6965
615 7105 6965
add 1700
615 1700
add 533
615 533
add 3145
615 3145 2503
add 6288
6288 615 7105 6965
add 2496
6288 615 3145 2496 2503
add 4305
6288 4810 4339 43...

output:

1 4339 
4339
2 615 4339 
615
3 615 4339 7105 
615
4 615 4339 4718 7105 
615
2 615 2503 
615
4 615 4718 4810 7105 
615
3 615 6965 7105 
615
2 615 1700 
615
2 533 615 
615
3 615 2503 3145 
615
4 615 6288 6965 7105 
6288
5 615 2496 2503 3145 6288 
6288
4 4305 4339 4810 6288 
6288
4 615 3145 3187 6288 
...

result:

ok n=8000, OK

Test #45:

score: 0
Accepted
time: 727ms
memory: 3888kb

input:

8000
add 4964
4964
add 3493
4964 3493
add 5110
4964 5110
add 533
4964 533 3493
add 1700
4964 1700 533
add 4277
4964 4277
add 2368
4964 2368 1700 3493
add 4495
4964 4495 4277
add 4305
4964 4305 4495 4277
add 6965
4964 6965
add 2503
4964 2503 2368
add 4339
4964 4339 4305
add 5195
4964 5195 5110
add 23...

output:

1 4964 
4964
2 3493 4964 
4964
2 4964 5110 
4964
3 533 3493 4964 
4964
3 533 1700 4964 
4964
2 4277 4964 
4964
4 1700 2368 3493 4964 
4964
3 4277 4495 4964 
4964
4 4277 4305 4495 4964 
4964
2 4964 6965 
4964
3 2368 2503 4964 
4964
3 4305 4339 4964 
4964
3 4964 5110 5195 
4964
4 2364 2368 2503 4964 
...

result:

ok n=8000, OK