QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700715#22. Power plantsTheZone100 ✓730ms31028kbC++239.3kb2024-11-02 13:19:382024-11-02 13:20:16

Judging History

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

  • [2024-11-02 13:20:16]
  • 评测
  • 测评结果：100
  • 用时：730ms
  • 内存：31028kb
查看
  • [2024-11-02 13:19:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
const ll INF = 1e18+7;
const int MAXN = 1e5+7;
pii t[MAXN]; bool vis[MAXN],k[MAXN],xd; pii p; int depth[MAXN],v1[MAXN],v2[MAXN];
vi g[MAXN]; int tmp,usu,n,rv1,rv2,rp;
struct str{int fi,sc,th;};
str pkt[MAXN];
bool comp(str a,str b){
	if(a.fi==b.fi) return a.sc<b.sc;
	else return a.fi<b.fi;
}
set<pii>s;
ll d(int x,int y){ 
	ll w1=t[x].fi, w2=t[x].sc, w3=t[y].fi, w4=t[y].sc;
	return (w1-w3)*(w1-w3)+(w2-w4)*(w2-w4); 
}
void DFS(int x,int f){
	if(xd==0) return;
	k[x]=1-k[f], vis[x]=1, depth[x]=depth[f]+1;
	for(auto s1:g[x]) 
		if(vis[s1]==1 and s1!=f and (depth[x]-depth[s1])%2==0 and k[x]==k[s1]){ xd=0; return; } 
		else if(vis[s1]==0) DFS(s1,x);
}
bool f(ll mid){
	xd=1; usu=0; int l=0,x,y;
	s.clear(); for(int i=0;i<rp;i++) g[pkt[i].th].clear(), vis[pkt[i].th]=0;
	ll prw=sqrt(mid);
	for(int i=0;i<rp;i++){
		//cout<<i<<'\n';
		l=0;
		x=pkt[i].fi, y=pkt[i].sc;
		while(x-pkt[usu].fi>prw) s.erase({pkt[usu].sc,pkt[usu].th}), usu++; 
		p={max((ll)0,y-prw),0};
		auto it=s.lower_bound(p);
		for(auto curr=it;curr!=s.end();curr++){
			l++;
			p=*curr;
			if(l>17) return 0;
			if(p.fi>y+prw) break;
			if(d(p.sc,pkt[i].th)<mid) g[pkt[i].th].pb(p.sc), g[p.sc].pb(pkt[i].th);
		}	
		s.insert({y,pkt[i].th});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) DFS(i,0);
		if(xd==0) break;
	}
	if(xd==1){
		rv1=rv2=0;
		for(int i=1;i<=n;i++) if(k[i]) v1[++rv1]=i; else v2[++rv2]=i;
	} 
	return xd;
}
void solve(){
	ll b=0,e=INF,mid,r=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].sc, pkt[rp++]={t[i].fi,t[i].sc,i};
	sort(pkt,pkt+rp,comp);
	while(b<=e){
		mid=(b+e)/2;
		if(f(mid)) r=mid, b=mid+1; else e=mid-1;
	}
	cout<<r<<'\n'<<rv1<<'\n';
	for(int i=1;i<=rv1;i++) cout<<v1[i]<<' '; cout<<'\n'<<rv2<<'\n';
	for(int i=1;i<=rv2;i++) cout<<v2[i]<<' '; cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt=1;
	while(tt--) solve();	
	return 0;
}

/*#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
const ll INF = 1e18+7;
const int MAXN = 1e5+7;
pii t[MAXN]; bool vis[MAXN],k[MAXN],xd; pii p; int depth[MAXN],v1[MAXN],v2[MAXN];
vi g[MAXN]; int tmp,usu,n,rv1,rv2,rp;
struct str{int fi,sc,th;};
str pkt[MAXN];
bool comp(str a,str b){
	if(a.fi==b.fi) return a.sc<b.sc;
	else return a.fi<b.fi;
}
set<pii>s;
ll d(int x,int y){ 
	ll w1=t[x].fi, w2=t[x].sc, w3=t[y].fi, w4=t[y].sc;
	return (w1-w3)*(w1-w3)+(w2-w4)*(w2-w4); 
}
void DFS(int x,int f){
	if(xd==0) return;
	k[x]=1-k[f], vis[x]=1, depth[x]=depth[f]+1;
	for(auto s1:g[x]) 
		if(vis[s1]==1 and s1!=f and (depth[x]-depth[s1])%2==0 and k[x]==k[s1]){ xd=0; return; } 
		else if(vis[s1]==0) DFS(s1,x);
}
bool f(ll mid){
	xd=1; usu=0; int l=0,x,y;
	s.clear(); for(int i=0;i<rp;i++) g[pkt[i].th].clear(), vis[pkt[i].th]=0;
	ll prw=sqrt(mid);
	for(int i=0;i<rp;i++){
		//cout<<i<<'\n';
		l=0;
		x=pkt[i].fi, y=pkt[i].sc;
		while(x-pkt[usu].fi>prw) s.erase({pkt[usu].sc,pkt[usu].th}), usu++; 
		p={max((ll)0,y-prw),0};
		auto it=s.lower_bound(p);
		for(auto curr=it;curr!=s.end();curr++){
			l++;
			p=*curr;
			if(l>17) return 0;
			if(p.fi>y+prw) break;
			if(d(p.sc,pkt[i].th)<mid) g[pkt[i].th].pb(p.sc), g[p.sc].pb(pkt[i].th);
		}	
		s.insert({y,pkt[i].th});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) DFS(i,0);
		if(xd==0) break;
	}
	if(xd==1){
		rv1=rv2=0;
		for(int i=1;i<=n;i++) if(k[i]) v1[++rv1]=i; else v2[++rv2]=i;
	} 
	return xd;
}
void solve(){
	ll b=0,e=INF,mid,r=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].sc, pkt[rp++]={t[i].fi,t[i].sc,i};
	sort(pkt,pkt+rp,comp);
	while(b<=e){
		mid=(b+e)/2;
		if(f(mid)) r=mid, b=mid+1; else e=mid-1;
	}
	cout<<r<<'\n'<<rv1<<'\n';
	for(int i=1;i<=rv1;i++) cout<<v1[i]<<' '; cout<<'\n'<<rv2<<'\n';
	for(int i=1;i<=rv2;i++) cout<<v2[i]<<' '; cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt=1;
	while(tt--) solve();	
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
const ll INF = 1e18+7;
const int MAXN = 1e5+7;
pii t[MAXN]; bool vis[MAXN],k[MAXN],xd; pii p; int depth[MAXN],v1[MAXN],v2[MAXN];
vi g[MAXN]; int tmp,usu,n,rv1,rv2,rp;
struct str{int fi,sc,th;};
str pkt[MAXN];
bool comp(str a,str b){
	if(a.fi==b.fi) return a.sc<b.sc;
	else return a.fi<b.fi;
}
set<pii>s;
ll d(int x,int y){ 
	ll w1=t[x].fi, w2=t[x].sc, w3=t[y].fi, w4=t[y].sc;
	return (w1-w3)*(w1-w3)+(w2-w4)*(w2-w4); 
}
void DFS(int x,int f){
	if(xd==0) return;
	k[x]=1-k[f], vis[x]=1, depth[x]=depth[f]+1;
	for(auto s1:g[x]) 
		if(vis[s1]==1 and s1!=f and (depth[x]-depth[s1])%2==0 and k[x]==k[s1]){ xd=0; return; } 
		else if(vis[s1]==0) DFS(s1,x);
}
bool f(ll mid){
	xd=1; usu=0; int l=0,x,y;
	s.clear(); for(int i=0;i<rp;i++) g[pkt[i].th].clear(), vis[pkt[i].th]=0;
	ll prw=sqrt(mid);
	for(int i=0;i<rp;i++){
		//cout<<i<<'\n';
		l=0;
		x=pkt[i].fi, y=pkt[i].sc;
		while(x-pkt[usu].fi>prw) s.erase({pkt[usu].sc,pkt[usu].th}), usu++; 
		p={max((ll)0,y-prw),0};
		auto it=s.lower_bound(p);
		for(auto curr=it;curr!=s.end();curr++){
			l++;
			p=*curr;
			if(l>17) return 0;
			if(p.fi>y+prw) break;
			if(d(p.sc,pkt[i].th)<mid) g[pkt[i].th].pb(p.sc), g[p.sc].pb(pkt[i].th);
		}	
		s.insert({y,pkt[i].th});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) DFS(i,0);
		if(xd==0) break;
	}
	if(xd==1){
		rv1=rv2=0;
		for(int i=1;i<=n;i++) if(k[i]) v1[++rv1]=i; else v2[++rv2]=i;
	} 
	return xd;
}
void solve(){
	ll b=0,e=INF,mid,r=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].sc, pkt[rp++]={t[i].fi,t[i].sc,i};
	sort(pkt,pkt+rp,comp);
	while(b<=e){
		mid=(b+e)/2;
		if(f(mid)) r=mid, b=mid+1; else e=mid-1;
	}
	cout<<r<<'\n'<<rv1<<'\n';
	for(int i=1;i<=rv1;i++) cout<<v1[i]<<' '; cout<<'\n'<<rv2<<'\n';
	for(int i=1;i<=rv2;i++) cout<<v2[i]<<' '; cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt=1;
	while(tt--) solve();	
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
const ll INF = 1e18+7;
const int MAXN = 1e5+7;
pii t[MAXN]; bool vis[MAXN],k[MAXN],xd; pii p; int depth[MAXN],v1[MAXN],v2[MAXN];
vi g[MAXN]; int tmp,usu,n,rv1,rv2,rp;
struct str{int fi,sc,th;};
str pkt[MAXN];
bool comp(str a,str b){
	if(a.fi==b.fi) return a.sc<b.sc;
	else return a.fi<b.fi;
}
set<pii>s;
ll d(int x,int y){ 
	ll w1=t[x].fi, w2=t[x].sc, w3=t[y].fi, w4=t[y].sc;
	return (w1-w3)*(w1-w3)+(w2-w4)*(w2-w4); 
}
void DFS(int x,int f){
	if(xd==0) return;
	k[x]=1-k[f], vis[x]=1, depth[x]=depth[f]+1;
	for(auto s1:g[x]) 
		if(vis[s1]==1 and s1!=f and (depth[x]-depth[s1])%2==0 and k[x]==k[s1]){ xd=0; return; } 
		else if(vis[s1]==0) DFS(s1,x);
}
bool f(ll mid){
	xd=1; usu=0; int l=0,x,y;
	s.clear(); for(int i=0;i<rp;i++) g[pkt[i].th].clear(), vis[pkt[i].th]=0;
	ll prw=sqrt(mid);
	for(int i=0;i<rp;i++){
		//cout<<i<<'\n';
		l=0;
		x=pkt[i].fi, y=pkt[i].sc;
		while(x-pkt[usu].fi>prw) s.erase({pkt[usu].sc,pkt[usu].th}), usu++; 
		p={max((ll)0,y-prw),0};
		auto it=s.lower_bound(p);
		for(auto curr=it;curr!=s.end();curr++){
			l++;
			p=*curr;
			if(l>17) return 0;
			if(p.fi>y+prw) break;
			if(d(p.sc,pkt[i].th)<mid) g[pkt[i].th].pb(p.sc), g[p.sc].pb(pkt[i].th);
		}	
		s.insert({y,pkt[i].th});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0) DFS(i,0);
		if(xd==0) break;
	}
	if(xd==1){
		rv1=rv2=0;
		for(int i=1;i<=n;i++) if(k[i]) v1[++rv1]=i; else v2[++rv2]=i;
	} 
	return xd;
}
void solve(){
	ll b=0,e=INF,mid,r=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].sc, pkt[rp++]={t[i].fi,t[i].sc,i};
	sort(pkt,pkt+rp,comp);
	while(b<=e){
		mid=(b+e)/2;
		if(f(mid)) r=mid, b=mid+1; else e=mid-1;
	}
	cout<<r<<'\n'<<rv1<<'\n';
	for(int i=1;i<=rv1;i++) cout<<v1[i]<<' '; cout<<'\n'<<rv2<<'\n';
	for(int i=1;i<=rv2;i++) cout<<v2[i]<<' '; cout<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tt=1;
	while(tt--) solve();	
	return 0;
}
*/
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 7804kb

input:

100
387 501
90 108
273 76
754 365
121 556
102 401
831 215
841 829
424 690
17 35
10 980
34 917
948 478
766 818
55 588
510 772
16 511
499 323
632 554
461 454
281 247
720 575
994 720
739 30
989 992
507 557
665 621
356 398
161 822
906 556
189 835
208 500
628 829
402 969
804 155
697 581
107 630
102 568
3...

output:

425
94
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 81 82 83 85 86 87 88 89 90 91 93 94 95 96 98 99 100 
6
40 49 75 84 92 97

result:

ok

Test #2:

score: 10
Accepted
time: 1ms
memory: 5752kb

input:

95
298 129
485 422
97 190
732 393
73 529
920 101
94 150
806 369
223 653
572 820
985 456
109 602
329 669
670 742
9 999
410 14
854 791
450 635
223 973
14 923
626 891
367 443
226 524
899 949
558 195
556 825
775 987
976 264
32 627
776 194
986 118
427 216
816 477
538 159
674 325
516 388
519 250
10 850
30...

output:

1530
81
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 30 31 32 33 34 35 36 37 38 39 41 42 45 47 49 51 52 53 54 56 57 58 59 60 61 62 63 64 66 67 68 69 71 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 89 91 92 93 95 
14
26 40 43 44 46 48 50 55 65 70 72 88 90 94

result:

ok

Test #3:

score: 10
Accepted
time: 1ms
memory: 7864kb

input:

97
45 2
63 84
71 62
15 8
23 74
33 30
87 92
50 25
55 44
36 69
36 20
58 61
19 72
28 33
96 72
93 14
98 62
85 62
4 33
55 54
86 91
86 60
82 27
46 39
16 61
85 37
11 74
11 48
97 96
9 71
46 14
6 70
37 32
17 93
39 98
27 22
79 44
86 1
55 15
66 19
41 97
71 61
83 23
87 62
13 48
72 56
47 68
45 82
10 88
96 96
71 ...

output:

5
88
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 46 47 48 49 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 81 84 85 86 87 88 89 90 91 92 93 95 96 97 
9
21 42 44 45 50 80 82 83 94

result:

ok

Test #4:

score: 10
Accepted
time: 0ms
memory: 7812kb

input:

95
292 500
313 500
687 500
500 480
791 500
500 916
875 500
438 500
583 500
645 500
500 979
500 520
916 500
937 500
500 604
500 500
500 812
500 625
500 105
500 791
500 937
146 500
417 500
500 334
396 500
42 500
459 500
500 770
355 500
500 854
500 645
500 313
500 271
500 146
334 500
958 500
501 501
50...

output:

8
93
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 85 86 87 88 89 90 91 92 93 94 95 
2
37 84

result:

ok

Test #5:

score: 10
Accepted
time: 0ms
memory: 7792kb

input:

99
815 111
6 579
250 933
336 972
555 3
12 389
990 405
55 270
790 907
6 420
106 190
460 998
492 0
71 756
617 985
995 563
586 992
197 102
397 989
839 867
678 32
736 59
920 229
30 328
964 685
149 143
975 343
648 22
88 783
902 203
127 833
964 314
41 299
249 66
30 671
428 5
0 515
586 7
366 981
995 436
49...

output:

1066
50
1 2 3 6 7 8 9 14 15 20 24 27 28 30 37 38 39 41 42 43 44 47 48 50 51 52 55 56 57 60 61 62 63 64 66 69 70 71 73 79 82 85 86 88 91 93 94 95 96 97 
49
4 5 10 11 12 13 16 17 18 19 21 22 23 25 26 29 31 32 33 34 35 36 40 45 46 49 53 54 58 59 65 67 68 72 74 75 76 77 78 80 81 83 84 87 89 90 92 98 99

result:

ok

Test #6:

score: 10
Accepted
time: 1ms
memory: 7780kb

input:

81
2 8
1 2
1 5
3 6
7 5
1 1
2 9
3 2
4 9
6 3
8 3
5 2
4 1
8 2
7 3
7 4
5 1
4 7
6 9
5 9
6 7
9 2
2 7
2 1
6 2
4 6
1 8
1 4
9 3
5 5
3 4
8 4
6 4
2 4
2 6
7 2
7 8
2 5
8 1
1 9
4 3
9 4
5 7
4 4
4 2
6 5
7 1
8 6
4 8
3 8
9 6
6 8
3 7
4 5
3 9
7 7
9 7
8 5
5 4
2 2
6 6
3 3
9 5
5 6
9 1
2 3
1 7
6 1
3 5
7 6
5 8
3 1
8 7
1 3
9...

output:

2
41
1 3 5 6 14 15 17 20 25 26 29 30 32 33 34 35 40 43 44 45 47 48 49 52 53 55 56 57 60 61 62 63 65 67 69 72 74 75 78 80 81 
40
2 4 7 8 9 10 11 12 13 16 18 19 21 22 23 24 27 28 31 36 37 38 39 41 42 46 50 51 54 58 59 64 66 68 70 71 73 76 77 79

result:

ok

Test #7:

score: 10
Accepted
time: 1ms
memory: 5632kb

input:

100
845 825
422 32
580 328
94 955
607 941
991 977
94 217
986 857
983 777
296 306
439 746
578 46
884 259
475 542
577 48
215 341
148 73
709 71
194 747
794 685
718 657
76 756
802 901
982 583
618 954
252 117
609 943
371 279
90 222
496 958
840 823
879 260
45 245
173 603
662 740
795 627
373 276
419 35
415...

output:

281
50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 28 30 33 34 35 36 39 40 42 43 44 45 46 47 48 51 53 54 55 57 64 65 68 69 90 
50
15 27 29 31 32 37 38 41 49 50 52 56 58 59 60 61 62 63 66 67 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 97 98 99 1...

result:

ok

Test #8:

score: 10
Accepted
time: 1ms
memory: 5692kb

input:

100
351 159
387 82
565 234
715 966
38 208
991 866
200 21
574 529
543 319
216 543
374 653
825 704
591 437
936 295
284 478
785 380
609 454
283 155
790 95
220 181
751 869
877 960
744 61
111 780
583 203
696 211
37 868
930 773
298 129
137 483
952 658
492 154
563 958
935 11
263 844
209 378
9 636
536 878
5...

output:

853
90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 89 90 92 94 95 96 97 98 99 
10
17 42 67 68 69 70 88 91 93 1...

result:

ok

Test #9:

score: 10
Accepted
time: 1ms
memory: 7792kb

input:

100
464 814
173 646
422 812
632 761
136 559
443 813
740 617
834 171
281 760
544 802
750 500
230 718
135 364
759 119
143 340
219 205
507 62
186 665
401 808
563 797
397 85
340 791
727 650
706 93
144 582
484 813
151 316
130 535
371 94
125 413
748 583
277 150
423 76
130 389
124 487
451 70
381 804
785 13...

output:

800
61
1 2 3 5 8 10 11 12 13 14 17 22 24 27 29 30 32 33 36 37 38 39 41 42 43 44 45 46 47 48 49 50 51 55 57 58 59 62 65 67 68 69 70 71 72 73 74 76 77 78 80 82 86 87 88 91 94 95 96 99 100 
39
4 6 7 9 15 16 18 19 20 21 23 25 26 28 31 34 35 40 52 53 54 56 60 61 63 64 66 75 79 81 83 84 85 89 90 92 93 97 ...

result:

ok

Subtask #2:

score: 25
Accepted

Dependency #1:

100%
Accepted

Test #10:

score: 25
Accepted
time: 8ms
memory: 5916kb

input:

2000
6656 36013
17956 38816
27582 2843
35098 36562
37326 25620
9311 12897
28300 8999
12801 12172
23738 23210
14428 6352
15922 13965
12936 32581
34742 14350
37329 23294
14140 35598
13133 19875
37742 36602
14322 6642
22080 14603
8989 7439
3353 31999
2980 18775
18422 1027
37749 20652
21614 27031
7197 2...

output:

6560
1974
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

result:

ok

Test #11:

score: 25
Accepted
time: 7ms
memory: 5940kb

input:

1814
21174 38708
32970 28661
27373 4800
28065 4522
32688 8747
16399 31278
24005 34303
33873 36750
15967 33261
4040 6842
7951 5550
31481 17924
39704 19328
35729 4162
36435 18728
37840 31349
17148 3065
32106 9758
14081 29393
19461 1956
11679 38126
37305 10201
14570 2250
35591 13991
21671 29312
37253 1...

output:

15245
1764
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

result:

ok

Test #12:

score: 25
Accepted
time: 6ms
memory: 5984kb

input:

1880
414 801
1765 607
1089 1518
773 100
32 1671
398 791
196 822
1435 432
713 206
931 842
1260 1585
1117 122
1606 642
885 1941
784 1996
1605 143
1337 1588
566 1858
363 1953
60 949
1618 1094
1360 1384
854 1750
486 844
380 1925
667 1216
1326 1369
1132 1418
1673 1659
121 1791
1985 41
947 130
1608 1774
1...

output:

29
1844
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

result:

ok

Test #13:

score: 25
Accepted
time: 5ms
memory: 6060kb

input:

1995
2045 20000
20000 21563
35430 20000
20000 38877
20000 7295
22885 20000
20000 11904
20000 30260
20000 22044
20000 16233
33787 20000
20000 25170
20000 31903
20000 8377
20000 31342
26012 20000
20000 34629
1123 20000
20000 34869
6453 20000
20000 19920
31462 20000
19159 20000
20000 10461
20000 33146
...

output:

8
1994
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok

Test #14:

score: 25
Accepted
time: 2ms
memory: 6328kb

input:

1999
3878 31836
39960 21256
178 17336
39849 22445
11239 2020
21178 39965
23114 244
19481 39993
3066 9358
39417 24793
26526 1094
36643 31090
10678 2304
17601 39855
9001 3295
36747 30932
32300 4229
10 19340
161 17460
38685 12868
39679 23564
39609 16065
38900 26540
6993 4806
27932 38359
22305 39866
717...

output:

4090
999
1 2 3 5 6 7 9 11 12 15 18 19 20 23 24 26 29 30 31 33 34 35 38 39 41 42 43 44 45 46 50 53 55 56 57 58 62 63 64 65 66 67 68 69 71 72 73 75 76 80 82 84 85 86 88 91 93 94 95 97 99 100 101 102 103 106 111 113 115 117 119 124 125 126 127 132 133 135 137 139 141 142 143 147 149 151 156 159 162 163...

result:

ok

Test #15:

score: 25
Accepted
time: 4ms
memory: 8064kb

input:

1936
27 6
26 15
27 18
5 17
31 3
40 18
36 18
22 9
8 1
36 33
40 27
7 16
14 30
23 9
43 17
42 21
26 36
9 44
33 16
35 23
8 27
12 28
33 31
19 22
11 30
11 37
35 8
29 33
9 38
33 15
35 19
40 24
17 25
6 41
32 8
8 43
35 11
23 32
42 15
34 5
8 22
25 9
5 25
15 42
22 7
27 8
2 32
33 29
30 20
21 17
20 8
33 18
7 1
20...

output:

2
968
1 2 3 8 9 10 11 12 16 18 19 21 24 25 27 29 34 36 38 39 40 44 45 46 52 54 55 58 59 60 61 62 66 67 71 72 74 76 78 79 80 83 85 87 92 93 94 101 102 103 106 108 111 112 116 117 118 119 121 124 125 126 127 130 131 134 135 138 139 140 144 145 146 148 149 151 155 156 160 166 167 169 172 178 180 181 18...

result:

ok

Test #16:

score: 25
Accepted
time: 6ms
memory: 8028kb

input:

1992
306 37924
38427 27958
8926 12030
27489 19285
38238 27286
17983 28458
1840 9861
27552 19604
7504 2884
19349 7486
10529 27553
39910 4330
34843 7397
31545 17158
18246 39978
10455 9952
39712 39598
38441 17586
17009 5364
24267 14406
27962 16744
27974 1812
22883 4112
6181 7896
37926 6732
11091 11855
...

output:

2138
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 97 98 99 100 101 102...

result:

ok

Test #17:

score: 25
Accepted
time: 5ms
memory: 5948kb

input:

2000
12637 20722
5811 21567
4662 39644
21724 25871
37976 22166
826 24747
39424 26287
15649 15481
13915 10224
1760 19764
14564 8363
29536 20965
3060 6764
32254 39746
26796 14893
35927 16726
37424 20568
21330 28438
31371 9999
19700 11073
3353 6335
39896 37387
30042 25198
2113 18543
25941 27908
39240 3...

output:

15250
1951
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

result:

ok

Test #18:

score: 25
Accepted
time: 5ms
memory: 6088kb

input:

2000
29399 25371
29911 23644
39298 16123
8402 27923
25861 2952
38856 14769
15020 32137
26905 3245
24695 2704
27611 3482
24590 30943
18897 32589
4935 17683
39021 15235
27588 28414
5377 14701
5095 16092
18540 2695
13320 31541
5018 20164
27395 3406
30080 20635
16148 32394
14700 32044
28395 27324
30122 ...

output:

3925
1012
1 3 5 6 7 10 11 12 13 14 16 18 20 21 23 24 26 27 28 31 33 37 40 42 43 44 45 46 47 50 52 54 55 57 58 60 61 62 63 64 66 67 69 70 72 73 74 75 77 79 85 90 93 94 96 97 99 100 104 106 109 110 112 114 115 121 124 127 130 131 132 133 134 136 138 139 140 141 143 144 145 146 147 149 151 153 154 155 ...

result:

ok

Subtask #3:

score: 65
Accepted

Dependency #2:

100%
Accepted

Test #19:

score: 65
Accepted
time: 683ms
memory: 12552kb

input:

100000
86906317 677293372
296132899 233592282
855515093 484310886
896196452 379278033
585155823 182058640
256572667 337258782
77013095 617791578
298155474 617701948
203022896 120906904
700113795 817766366
10932305 828355830
601157685 66977660
84465578 493682621
37027543 713776658
323862182 770128858...

output:

29023118617
99488
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

result:

ok

Test #20:

score: 65
Accepted
time: 631ms
memory: 12260kb

input:

91743
578366302 927433638
71023543 137807206
294318266 338014821
964689287 252905228
220392227 696876231
919459690 810526230
68400622 189922973
783715277 844662230
738992157 434157447
415674312 625021643
185627558 311456999
903997362 72735941
391659615 24822653
847123746 807146317
716927270 27228801...

output:

29460406042
91336
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

result:

ok

Test #21:

score: 65
Accepted
time: 352ms
memory: 13272kb

input:

98595
2082 28980
6196 92631
29892 27425
98594 88352
57561 95089
45551 66077
34734 62451
67272 59109
14759 36907
72279 89460
24055 56824
2918 7715
33815 35878
86740 13434
54603 13141
98349 96408
29069 10950
66766 17421
50974 55869
54248 44747
4111 6018
76243 70533
11463 37947
7500 27076
928 18088
894...

output:

353
98061
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

result:

ok

Test #22:

score: 65
Accepted
time: 470ms
memory: 28084kb

input:

99995
811292451 500000000
500000000 509840393
500000000 628225129
135185408 500000000
500000000 738109524
707368294 500000000
500000000 680307212
500000000 661546461
64002561 500000000
500000000 564602584
585903436 500000000
18140726 500000000
500000000 524800992
230389216 500000000
253690148 500000...

output:

8
99994
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

result:

ok

Test #23:

score: 65
Accepted
time: 433ms
memory: 31028kb

input:

99999
997450171 550431412
418331904 993285234
582520317 993143384
479828395 407059
412912942 7642564
898003259 197355975
56882346 731617670
61855438 740892804
949288858 280592794
742027594 62481265
191382625 893389522
36601915 687782362
212308550 91057913
991602459 408747482
743510679 63304970
51215...

output:

987056680
50000
1 2 3 4 5 8 9 10 11 15 17 19 20 22 23 26 27 28 30 33 34 36 39 40 41 43 45 48 53 54 55 56 57 58 59 60 63 66 67 70 73 78 79 81 85 86 90 91 93 96 98 99 100 102 103 111 112 113 117 118 120 128 130 132 133 138 139 141 142 145 146 150 151 152 153 154 158 162 163 165 166 167 174 175 176 177...

result:

ok

Test #24:

score: 65
Accepted
time: 150ms
memory: 24988kb

input:

99856
305 78
185 223
103 79
38 113
168 135
312 147
202 55
274 15
89 90
96 143
11 52
206 238
182 227
3 50
142 163
20 300
140 251
118 37
145 21
231 154
150 21
153 223
124 50
254 298
180 69
7 4
174 20
8 241
239 164
154 282
106 186
11 218
45 123
238 312
126 249
42 111
127 71
160 77
129 12
298 18
215 197...

output:

2
49928
1 4 5 6 7 8 9 10 11 13 14 15 17 18 20 21 25 26 28 29 32 35 36 38 39 43 45 48 51 53 54 55 58 60 62 63 64 66 67 68 69 71 75 77 79 81 82 86 87 89 90 93 94 95 100 102 103 106 107 108 109 110 112 113 114 120 121 122 124 129 132 133 134 135 136 138 141 144 145 146 147 149 150 153 154 156 159 160 1...

result:

ok

Test #25:

score: 65
Accepted
time: 504ms
memory: 12908kb

input:

99521
141042363 89491445
469322351 365495982
353719483 948010497
615938040 258706079
680242542 559864723
574606403 305078347
913240642 978892350
128440632 535274846
149965767 654239680
504436456 35604103
96934630 938551477
31524409 601512784
635452664 312972306
410719949 432007286
634269718 63563199...

output:

585256433
50000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

result:

ok

Test #26:

score: 65
Accepted
time: 730ms
memory: 13232kb

input:

100000
998357611 31436018
223544476 30057220
675430006 288074149
434210883 335374061
629397359 111950068
737202797 774741429
426822825 479813640
29949399 157030324
903152268 416630858
643648519 445607548
725128645 480749433
373173056 803752391
459028971 137528873
429175672 662062003
843395645 240277...

output:

38995488925
99381
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...

result:

ok

Test #27:

score: 65
Accepted
time: 477ms
memory: 26480kb

input:

100000
409827459 80506748
134135815 551356606
922701497 271914546
150707196 317336470
577192487 62308992
997346456 474790833
122932288 464487000
243376127 731742953
991324794 439058163
526692240 60894836
190298126 672975000
983435733 406485488
927817099 279939128
123144880 447124734
573185681 793808...

output:

968000000
51288
1 3 5 6 9 10 11 12 13 15 16 18 21 22 27 28 33 34 35 36 37 41 42 43 48 52 58 59 62 63 65 68 70 72 73 74 76 79 80 81 82 84 85 87 90 91 94 97 99 100 101 102 103 104 105 106 108 109 110 111 112 116 117 118 121 122 123 124 125 128 130 131 132 133 134 135 138 140 141 145 149 150 151 154 15...

result:

ok

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 02:46:10 | OpenSource Project