QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873593#9685. nim 游戏JohnAlfnov84 73ms86880kbC++144.5kb2025-01-26 17:56:112025-01-26 17:56:11

Judging History

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

  • [2025-01-27 09:19:35]
  • hack成功,自动添加数据
  • (/hack/1490)
  • [2025-01-27 08:19:11]
  • hack成功,自动添加数据
  • (/hack/1488)
  • [2025-01-26 18:55:44]
  • hack成功,自动添加数据
  • (/hack/1475)
  • [2025-01-26 17:56:11]
  • 评测
  • 测评结果:84
  • 用时:73ms
  • 内存:86880kb
  • [2025-01-26 17:56:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace file_read{
	char ib[1<<24],*ip1=ib,*ip2=ib;
	inline char gc(){
		return ((ip1==ip2)&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++);
	}
	inline int read(){
		int x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
	inline long long readl(){
		long long x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
}
using namespace file_read;
long long a[100005];
int n,m;
long long ann;
namespace yuchu{
	long long b[100005];
	void solve(){
		for(int i=1;i<=n;++i)b[i]=a[i];
		long long ans=0;
		for(int t=59;t>=0;--t){
			int gs=0;
			for(int i=1;i<=n;++i)if(b[i]>>t&1)++gs;
			if(gs%2==0)continue;
			if(gs<n)break;
			for(int tt=t;tt<=59;++tt){
				int gs=0;
				for(int i=1;i<=n;++i)if(b[i]>>tt&1)++gs;
				if(gs<n)break;
				long long T=(1ll<<(tt+1))-1;
				long long mx=-1;int wz=0;
				for(int i=1;i<=n;++i){
					if(mx<b[i])mx=b[i],wz=i;
				}
				mx=b[wz]&T;++T;
				ans+=T-mx;b[wz]+=T-mx;
			}
		}
		for(int t=60;t>=0;--t){
			int gs=0;
			for(int i=1;i<=n;++i)if(b[i]>>t&1)++gs;
			if(gs%2==0)continue;
			long long T=(1ll<<(t+1))-1;
			long long mx=-1;int wz=0;
			for(int i=1;i<=n;++i){
				if((b[i]&T)>=(1ll<<t))continue;
				if(mx<(b[i]&T))mx=(b[i]&T),wz=i;
			}
			ans+=(1ll<<t)-mx;b[wz]+=(1ll<<t)-mx;
		}
		ann=ans;printf("%lld\n",ans);
	}
}
namespace baoli{
	long long aj[100005];
	int p2[100005];
	int tt;vector<pair<int,long long>>vv[20005];
	long long aa[65][100005];
	int hh[65],pp[65][100005];
	int tj[100005],st[105],sl=0;
	bool dfs(int t,long long he){
		if(t<0){
			if(he>ann)return 0;
			--m;
			vector<pair<int,long long>>vc;
			for(int i=1;i<=sl;++i){
				int x=st[i];
				if(aj[x])vc.emplace_back(x,aj[x]);
			}
			sort(vc.begin(),vc.end());
			vv[++tt]=vc;
			return 1;
		}
		int gs=hh[t];
		for(int i=1;i<=sl;++i){
			int j=st[i];
			gs-=aa[t][j]>>t&1;
		}
		if(gs%2==0)return dfs(t-1,he);
		if(gs==n)return 0;
		int fl=0,cg=1;
		for(int i=n-gs;i>=1&&cg&&m;--i){
			int j=pp[t][i];
			if(tj[j])continue;
			if((aa[t][j]>>t&1))continue;
			long long sb=(1ll<<t)-aa[t][j];
			aj[j]+=sb;++tj[j];
			if(tj[j]==1)st[++sl]=j;
			int ff=1;
			if(dfs(t-1,he+sb))fl=1;
			else ff=0;
			if(tj[j]==1)--sl;
			--tj[j];aj[j]-=sb;
			if(!ff)return fl;
		}
		for(int i=1;i<=sl&&cg&&m;++i){
			int j=st[i];
			long long sb=(1ll<<t)-0;
			aj[j]+=sb;++tj[j];
			if(tj[j]==1)st[++sl]=j;
			int ff=1;
			if(dfs(t-1,he+sb))fl=1;
			else ff=0;
			if(tj[j]==1)--sl;
			--tj[j];aj[j]-=sb;
			if(!ff)return fl;
		}
		return fl;
	}
	void solve(){
		for(int i=1;i<=n;++i)p2[i]=i;
		sort(p2+1,p2+n+1,[&](int x,int y){
			return a[x]<a[y];
		});
		for(int t=60;t>=0;--t){
			hh[t]=0;
			int w=0;
			for(int i=1;i<=n;++i){
				aa[t][i]=a[i]&((1ll<<(t+1))-1);
				pp[t][i]=p2[i];hh[t]+=(aa[t][i]>>t&1);
			}
			for(int i=1;i<=n;++i){
				if(aa[t][p2[i]]<(1ll<<t))w=i;
			}
			inplace_merge(p2+1,p2+w+1,p2+n+1,[&](int x,int y){
				return (a[x]&((1ll<<t)-1))<(a[y]&((1ll<<t)-1));
			});
		}
		for(int i=1;i<=n;++i)aj[i]=0;
		tt=0;dfs(59,0);
	}
	void solve2(){
		for(int t=60;t>=1;--t){
			int gs=0;
			for(int j=1;j<=n;++j)gs+=(a[j]>>t&1);
			if(gs%2)break;
			int w=0;
			for(int j=n;j>=1;--j){
				if(aa[t][pp[t][j]]>=(1ll<<t))continue;
				w=j;break;
			}
			for(int j=w;j>=2;--j){
				int ff=0;
				for(int k=j-1;k>=1;--k){
					int x=pp[t][j],y=pp[t][k];
					st[++sl]=x;st[++sl]=y;
					++tj[x];++tj[y];
					aj[x]+=(1ll<<t)-aa[t][x];
					aj[y]+=(1ll<<t)-aa[t][y];
					if(!dfs(t-1,(2ll<<t)-aa[t][x]-aa[t][y])){
						--tj[x];--tj[y];--sl;--sl;
						aj[x]-=(1ll<<t)-aa[t][x];
						aj[y]-=(1ll<<t)-aa[t][y];
						break;
					}
					--tj[x];--tj[y];--sl;--sl;++ff;
					aj[x]-=(1ll<<t)-aa[t][x];
					aj[y]-=(1ll<<t)-aa[t][y];
				}
				if(!ff)break;
			}
		}
	}
	void output(){
		printf("%d\n",tt);
		for(int i=1;i<=tt;++i){
			vector<pair<int,long long>>vc=vv[i];
			sort(vc.begin(),vc.end());
			int z=vc.size();
			printf("%d\n",z);
			for(int j=0;j<z;++j)printf("%d ",vc[j].first);
			printf("\n");
			for(int j=0;j<z;++j)printf("%lld ",vc[j].second);
			printf("\n");
		}
	}
}
int main(){
	int c=read(),T=read();
	assert(c>=0);
	while(T--){
		n=read(),m=read();
		for(int i=1;i<=n;++i)a[i]=readl();
		yuchu::solve();
		baoli::solve();
		if(n%2)baoli::solve2();
		baoli::output();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 22ms
memory: 81748kb

input:

1 10000
2 1
324097321 555675086
2 1
304655177 991244276
2 1
9980291 383616352
2 1
1071036550 795625380
2 1
682098056 68370721
2 1
969101726 685975156
2 1
973896269 354857775
2 1
196188000 606494155
2 1
754416123 467588829
2 1
495704303 558090120
2 1
618002000 491488050
2 1
741575237 9937018
2 1
1002...

output:

231577765
1
1
1 
231577765 
686589099
1
1
1 
686589099 
373636061
1
1
1 
373636061 
275411170
1
1
2 
275411170 
613727335
1
1
2 
613727335 
283126570
1
1
2 
283126570 
619038494
1
1
2 
619038494 
410306155
1
1
1 
410306155 
286827294
1
1
2 
286827294 
62385817
1
1
1 
62385817 
126513950
1
1
2 
12651...

result:

ok correct answer

Subtask #2:

score: 12
Accepted

Test #2:

score: 12
Accepted
time: 0ms
memory: 81748kb

input:

2 5
5 2000
0 13 3 4 10
5 2000
0 3 9 1 11
5 2000
0 13 7 3 5
5 2000
0 1 13 9 2
5 2000
0 8 14 7 13

output:

0
1
0


0
1
0


2
2
2
2 3 
1 1 
2
3 5 
1 1 
3
2
2
1 5 
1 2 
1
5 
3 
2
1
2
4 5 
1 1 

result:

ok correct answer

Test #3:

score: 12
Accepted
time: 1ms
memory: 81624kb

input:

2 5
5 2000
0 4 14 5 7
5 2000
0 2 15 0 12
5 2000
0 1 14 0 5
5 2000
0 13 4 12 3
5 2000
0 10 10 1 11

output:

6
2
3
1 4 5 
4 1 1 
2
4 5 
1 5 
1
4
1
2 
1 
1
5 
1 
1
4 
1 
1
1 
1 
8
8
3
2 4 5 
3 2 3 
3
1 2 5 
2 3 3 
2
2 5 
3 5 
2
2 5 
5 3 
3
2 4 5 
1 4 3 
3
1 2 5 
4 1 3 
2
2 5 
1 7 
2
2 5 
7 1 
2
4
2
4 5 
1 1 
2
3 5 
1 1 
2
1 5 
1 1 
1
5 
2 
10
13
3
1 3 4 
2 1 7 
3
1 2 4 
2 1 7 
2
1 4 
2 8 
2
1 4 
3 7 
2
3 4 ...

result:

ok correct answer

Test #4:

score: 12
Accepted
time: 0ms
memory: 81744kb

input:

2 5
5 2000
0 6 15 10 1
5 2000
0 15 0 13 10
5 2000
0 5 7 5 1
5 2000
0 13 3 2 15
5 2000
0 2 4 7 0

output:

2
5
2
2 5 
1 1 
2
4 5 
1 1 
2
1 5 
1 1 
1
5 
2 
1
1 
2 
8
2
1
3 
8 
1
1 
8 
4
2
2
4 5 
1 3 
2
2 5 
1 3 
1
1
1
2 
1 
1
4
1
2 
1 
1
3 
1 
1
5 
1 
1
1 
1 

result:

ok correct answer

Subtask #3:

score: 12
Accepted

Dependency #2:

100%
Accepted

Test #5:

score: 12
Accepted
time: 1ms
memory: 81876kb

input:

3 5
6 2000
0 45 517 811 107 132
6 2000
0 382 576 805 419 579
6 2000
0 379 809 441 331 67
6 2000
0 565 776 959 852 383
6 2000
0 613 383 829 47 441

output:

146
20
5
1 2 3 5 6 
1 19 1 1 124 
4
2 3 5 6 
19 1 1 125 
4
2 3 5 6 
20 1 1 124 
4
2 3 5 6 
19 1 2 124 
4
2 3 5 6 
19 2 1 124 
4
1 2 5 6 
2 19 1 124 
3
2 5 6 
19 1 126 
3
2 5 6 
21 1 124 
3
2 5 6 
19 3 124 
5
1 2 3 4 6 
1 19 1 1 124 
4
2 3 4 6 
19 1 1 125 
4
2 3 4 6 
20 1 1 124 
4
2 3 4 6 
19 1 2 124...

result:

ok correct answer

Test #6:

score: 12
Accepted
time: 1ms
memory: 81744kb

input:

3 5
6 2000
0 75 173 555 637 905
6 2000
0 934 118 906 367 728
6 2000
0 244 321 598 625 469
6 2000
0 573 489 24 480 459
6 2000
0 424 356 750 623 871

output:

557
483
5
1 2 3 5 6 
8 53 342 131 23 
5
1 2 3 5 6 
8 53 341 132 23 
5
1 2 3 5 6 
8 54 341 131 23 
5
1 2 3 5 6 
8 53 341 131 24 
5
1 2 3 5 6 
9 53 341 131 23 
5
1 2 3 5 6 
8 53 340 133 23 
5
1 2 3 5 6 
8 53 339 134 23 
5
1 2 3 5 6 
8 54 339 133 23 
5
1 2 3 5 6 
8 53 339 133 24 
5
1 2 3 5 6 
9 53 339 ...

result:

ok correct answer

Test #7:

score: 12
Accepted
time: 2ms
memory: 81872kb

input:

3 5
6 2000
0 886 972 226 813 407
6 2000
0 219 190 742 101 572
6 2000
0 590 423 516 1017 46
6 2000
0 388 807 207 205 647
6 2000
0 408 180 238 300 694

output:

176
25
5
1 2 4 5 6 
8 10 30 19 109 
5
1 2 4 5 6 
8 10 34 19 105 
5
1 2 4 5 6 
8 14 30 19 105 
5
1 2 4 5 6 
8 10 30 23 105 
5
1 2 4 5 6 
12 10 30 19 105 
5
1 2 4 5 6 
4 10 30 19 113 
4
2 4 5 6 
10 30 19 117 
4
2 4 5 6 
10 34 19 113 
4
2 4 5 6 
14 30 19 113 
4
2 4 5 6 
10 30 23 113 
5
1 2 4 5 6 
4 10 ...

result:

ok correct answer

Subtask #4:

score: 12
Accepted

Test #8:

score: 12
Accepted
time: 34ms
memory: 81860kb

input:

4 257
100000 100
32768 65536 262144 32768 8388608 1048576 4 67108864 16384 32768 262144 8192 512 134217728 65536 4194304 262144 67108864 1024 262144 64 32 65536 2097152 268435456 1 2048 4194304 16777216 8 16384 2 2048 16777216 268435456 262144 1048576 8388608 16 268435456 2 128 4194304 262144 32768 ...

output:

303389274
100
13
1529 3182 13132 13340 14843 15944 25699 38912 49506 66548 80730 86025 98687 
65536 8 512 16 262144 1048576 2048 33554432 268435456 64 2 16384 4096 
13
1529 3182 13132 13340 14843 15944 24098 25699 38912 49506 66548 86025 98687 
65536 8 512 16 262144 1048576 2 2048 33554432 268435456...

result:

ok correct answer

Test #9:

score: 12
Accepted
time: 33ms
memory: 85116kb

input:

4 266
100000 100
134217728 524288 8388608 4 8 8388608 33554432 4 536870912 4 16 8 33554432 33554432 256 65536 8 16 64 8 256 2048 268435456 256 8192 2 1024 65536 32 2048 134217728 8 1048576 8 16777216 33554432 1024 33554432 131072 16 2 33554432 8192 512 4194304 2048 268435456 256 536870912 16777216 1...

output:

269988539
100
15
1323 1751 7003 8582 11559 12180 14102 36361 38465 41745 52631 62405 68001 83584 95151 
32 1 8 32768 131072 65536 8192 4096 512 268435456 16 128 1048576 2 262144 
15
1323 7003 8582 11559 12180 14102 22275 36361 38465 41745 52631 62405 68001 83584 95151 
32 8 32768 131072 65536 8192 1...

result:

ok correct answer

Test #10:

score: 12
Accepted
time: 36ms
memory: 82140kb

input:

4 269
100000 100
1048576 2 64 67108864 1024 67108864 268435456 32768 8388608 32 256 2 268435456 262144 524288 262144 2 524288 64 8192 262144 536870912 2097152 64 1024 2 1048576 128 2 8388608 512 32768 1 8388608 4 2 268435456 128 67108864 65536 2 8388608 2048 16 2048 4096 32768 1048576 32768 32 83886...

output:

471323918
100
15
366 3033 14022 18335 31197 34895 50650 55459 62700 69653 73127 81097 83750 87272 88617 
32768 134217728 4096 256 65536 131072 67108864 1024 1048576 16384 262144 268435456 8 4 2 
15
366 3033 14022 18335 31197 34895 50650 55459 62700 69653 73127 81097 83750 83819 87272 
32768 13421772...

result:

ok correct answer

Test #11:

score: 12
Accepted
time: 66ms
memory: 85852kb

input:

4 2
100000 5000
32768 2 1024 1 65536 32768 4194304 4 2 33554432 1048576 268435456 4194304 268435456 268435456 4194304 32768 2097152 131072 16777216 1024 262144 2048 65536 512 1024 8388608 128 512 33554432 1 32 134217728 8388608 2097152 4 2097152 1048576 1024 33554432 536870912 536870912 33554432 327...

output:

362412129
5000
15
17128 28910 31657 32056 36479 38917 41679 43057 56220 57487 58751 63380 75915 80194 92057 
67108864 65536 1 32768 2048 4096 16384 64 524288 16777216 1048576 8192 268435456 32 8388608 
15
17128 28910 32056 36479 38917 41679 43057 56220 57487 58751 63380 75915 76033 80194 92057 
6710...

result:

ok correct answer

Test #12:

score: 12
Accepted
time: 40ms
memory: 86880kb

input:

4 1
100000 10000
32 536870912 4194304 32768 8 16777216 16384 32768 131072 131072 128 8192 32 32 256 4096 8 268435456 65536 1024 64 1024 4194304 4194304 128 268435456 2097152 64 8192 1048576 33554432 128 4194304 16 134217728 128 16384 4 33554432 67108864 2048 33554432 524288 1048576 4 4096 268435456 ...

output:

454096
10000
11
1004 11708 18711 22145 24019 32785 34315 44220 53202 61329 82730 
256 128 64 16384 131072 262144 2048 8192 1024 16 32768 
11
1004 11708 18711 22145 24019 32785 34315 44220 53202 82730 93472 
256 128 64 16384 131072 262144 2048 8192 1024 32768 16 
11
1004 11708 18711 22145 24019 32785...

result:

ok correct answer

Test #13:

score: 12
Accepted
time: 60ms
memory: 83796kb

input:

4 10000
20 1
536870912 131072 2048 8388608 2097152 128 4 67108864 8 128 1048576 8388608 32768 8 2097152 2 256 512 256 8388608
20 1
67108864 134217728 64 8 1024 134217728 536870912 256 268435456 65536 16777216 4 4096 4194304 131072 16384 128 16384 65536 2
20 1
16 1048576 16384 33554432 131072 128 204...

output:

477201922
1
6
5 8 11 13 16 18 
6291456 469762048 1048576 98304 2 1536 
322833594
1
7
4 5 9 11 15 17 20 
56 3072 268435456 50331648 4063232 128 2 
437384810
1
9
2 4 11 12 14 15 17 18 20 
1048576 33554432 402653184 12288 2 96 8 114688 1536 
28919934
1
7
1 5 7 11 13 19 20 
16384 25165824 2048 14 112 36...

result:

ok correct answer

Test #14:

score: 12
Accepted
time: 59ms
memory: 81752kb

input:

4 100
2000 100
524288 1 4096 16 32768 8 2048 262144 512 512 268435456 2048 256 32 1048576 524288 536870912 134217728 2048 64 33554432 65536 4 8388608 512 67108864 67108864 1048576 8388608 524288 256 4096 32 131072 536870912 2 8388608 2 67108864 128 32 8192 67108864 268435456 524288 8388608 8388608 1...

output:

352738786
100
14
238 374 439 474 751 929 1088 1159 1404 1412 1687 1692 1868 1888 
1024 262144 131072 128 2048 2 16777216 32 256 64 4096 67108864 268435456 16384 
14
238 374 439 474 751 1088 1159 1404 1412 1687 1692 1868 1888 1914 
1024 262144 131072 128 2048 16777216 32 256 64 4096 67108864 26843545...

result:

ok correct answer

Test #15:

score: 12
Accepted
time: 29ms
memory: 83820kb

input:

4 1
69901 10000
524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 5242...

output:

280444
10000
12
4817 14918 31895 33750 34660 40418 41401 45958 52827 65235 65236 69254 
262144 16384 1024 512 256 64 32 16 8 2 1 1 
12
4817 14918 31895 33750 34660 40418 41401 45958 52827 65235 65237 69254 
262144 16384 1024 512 256 64 32 16 8 2 1 1 
12
4817 14918 31895 33750 34660 40418 41401 45958...

result:

ok correct answer

Test #16:

score: 12
Accepted
time: 33ms
memory: 82788kb

input:

4 2
48360 5000
524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 524288 52428...

output:

253569
5000
10
7088 8810 10444 13052 20971 23421 25904 28129 32879 47457 
131072 65536 32768 16384 4096 2048 1024 512 128 1 
10
7088 8810 10444 13052 20971 23421 25904 28129 32879 47456 
131072 65536 32768 16384 4096 2048 1024 512 128 1 
10
7088 8810 10444 13052 20971 23421 25904 28129 32879 47455 
...

result:

ok correct answer

Test #17:

score: 12
Accepted
time: 8ms
memory: 83660kb

input:

4 100
34 100
536870912 536870912 268435456 134217728 67108864 67108864 33554432 16777216 8388608 1048576 524288 262144 131072 65536 65536 32768 32768 16384 8192 8192 4096 4096 2048 2048 1024 512 512 64 64 32 32 16 4 4
36 100
536870912 536870912 268435456 134217728 134217728 67108864 67108864 1677721...

output:

158712816
100
11
4 8 10 12 14 16 18 26 28 30 32 
134217728 16777216 7340032 262144 65536 32768 16384 512 448 32 16 
11
4 8 10 12 14 16 18 26 28 31 32 
134217728 16777216 7340032 262144 65536 32768 16384 512 448 32 16 
10
4 8 10 12 14 16 18 26 28 32 
134217728 16777216 7340032 262144 65536 32768 1638...

result:

ok correct answer

Subtask #5:

score: 12
Accepted

Test #18:

score: 12
Accepted
time: 32ms
memory: 83792kb

input:

5 10000
10 1
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823
10 1
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823
10 1
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741...

output:

1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 
...

result:

ok correct answer

Test #19:

score: 12
Accepted
time: 73ms
memory: 83856kb

input:

5 2323
100000 1
0 3170633 888529329 347839787 101667249 273239696 1028446182 411994109 710973319 298677951 299452068 519308796 361451040 488605068 74238166 997794448 478367019 532094220 747266199 217905213 682359917 774814810 234838947 456387659 38459020 434013070 633290806 173828476 94076883 568288...

output:

11962
1
15
5529 8448 10477 25124 33798 38129 47454 49541 59383 77917 78515 81987 83908 85254 92029 
19 54 1 1 8212 139 1 2165 1 1 1364 1 1 1 1 
1607036
1
11
4 6 7 12 15 16 22 26 28 29 36 
65471 32512 6 520064 978944 6136 3836 4 60 2 1 
106
1
3
1 2 3 
32 29 45 
3
1
2
2 5 
1 2 
126
1
5
3 4 5 9 10 
12 ...

result:

ok correct answer

Test #20:

score: 12
Accepted
time: 69ms
memory: 83468kb

input:

5 2205
100000 1
0 684191025 220215685 982495864 602362406 687396179 439432236 81065680 398068897 269754402 306183653 309939439 664994998 1011962742 338161922 629593565 926305057 1026259775 711874360 69406110 426672919 208267066 551253027 9384823 26156203 778817402 654214308 527029151 1065024353 2870...

output:

22539
1
18
9642 11813 14681 14972 21599 23957 38540 38873 40895 51780 55036 61870 62629 78388 89268 92172 92825 94825 
18405 5 1 1 2826 1 14 846 1 1 1 1 1 1 404 1 28 1 
5296170
1
10
8 9 11 14 16 19 20 23 30 38 
1048320 64 4194240 30 6142 31744 15360 2 16 252 
2997548
1
3
3 4 5 
7998 1031664 1957886 ...

result:

ok correct answer

Test #21:

score: 12
Accepted
time: 73ms
memory: 86672kb

input:

5 2166
100000 1
0 58930516 543560994 783997157 728082180 789115629 549794748 81818067 214839912 203394814 711969322 908524000 570262778 992867922 359455295 88035653 412186516 937931728 331800409 545354553 535440658 894562512 657466952 555070606 469471475 1055263866 874958292 76960239 478302168 68009...

output:

8241
1
16
66 13383 20904 24606 26786 29190 37436 53935 54258 58804 61496 68234 72809 82425 91630 96789 
63 1 1 1 5 7798 1 1 156 1 1 192 4 14 1 1 
2846999
1
4
1 2 4 5 
131072 103522 2049874 562531 
1605
1
6
6 7 8 12 18 21 
96 4 1023 480 1 1 
21150
1
4
1 2 3 5 
32 13220 4050 3848 
13
1
2
1 2 
4 9 
0
1...

result:

ok correct answer

Subtask #6:

score: 16
Accepted

Test #22:

score: 16
Accepted
time: 0ms
memory: 81744kb

input:

6 23
1000 10
0 357293452 452461848 986047039 546588280 762710079 767831017 39741545 416114273 515599366 1018969624 603342125 928112286 1053016142 240953466 533088067 1028134429 504727014 371307863 834428873 968387878 478550336 1047217797 1046651542 777749850 866989319 92995163 251915198 363285573 10...

output:

264227
10
12
85 134 203 355 565 673 677 786 876 955 996 999 
1 5 2638 9 531 1 1 697 251113 10 5226 3995 
12
85 134 203 355 565 673 748 786 876 955 996 999 
1 5 2638 9 531 1 1 697 251113 10 5226 3995 
12
85 132 134 203 355 565 673 786 876 955 996 999 
1 1 5 2638 9 531 1 697 251113 10 5226 3995 
12
59...

result:

ok correct answer

Test #23:

score: 16
Accepted
time: 0ms
memory: 81492kb

input:

6 23
1000 10
0 978686021 287986921 276311856 889616598 739968417 1060147652 463275477 172393699 591333230 983197307 235514434 330494755 449056272 882229818 781111474 275587745 980041928 334198691 305313012 415758352 947298893 950211162 909723054 961622596 917454340 161928901 404346316 369133631 1038...

output:

709905
10
15
32 159 163 279 283 347 482 656 677 727 842 917 954 977 978 
56 1 1 3862 6 1 12836 4 1 47 693086 1 1 1 1 
15
32 159 163 279 283 347 482 608 656 677 727 842 917 977 978 
56 1 1 3862 6 1 12836 1 4 1 47 693086 1 1 1 
15
32 159 163 279 283 347 482 656 677 727 761 842 917 977 978 
56 1 1 3862...

result:

ok correct answer

Test #24:

score: 16
Accepted
time: 2ms
memory: 81756kb

input:

6 15
1000 10
0 631723071 149784582 965844254 515554472 887253148 467825521 981769969 1054193550 627909969 590277818 159342752 658063143 667914173 169490051 25536270 337269419 1056885019 980490575 750858271 553446484 347553447 376197986 1053224035 473470890 123586 97769047 761755924 510998818 2560945...

output:

737485
10
15
162 172 265 384 387 474 599 625 643 747 790 831 880 924 960 
1 27 227 215546 1 2917 6 7 1 87404 1600 16 41649 388082 1 
15
65 162 172 265 384 387 474 599 625 643 747 790 831 880 924 
1 1 27 227 215546 1 2917 6 7 1 87404 1600 16 41649 388082 
15
162 172 265 384 387 474 599 625 643 747 79...

result:

ok correct answer

Test #25:

score: 16
Accepted
time: 0ms
memory: 81624kb

input:

6 25
1000 10
0 751950140 901599329 987895071 306253500 278530668 539473653 911723672 948474628 722632384 369217860 428703545 999113214 567923990 53499297 1013528916 263060554 669297221 349021033 832596533 893306880 892438572 345611286 331257977 488113061 578929864 881846255 320356815 76057168 704694...

output:

1119212
10
14
69 97 122 215 236 430 431 528 552 555 576 717 887 950 
1 7 5641 149775 107 1 6002 26620 674 1 1237 6239 922903 4 
14
97 122 215 236 307 430 431 528 552 555 576 717 887 950 
7 5641 149775 107 1 1 6002 26620 674 1 1237 6239 922903 4 
14
97 122 215 236 430 431 528 552 555 576 685 717 887 ...

result:

ok correct answer

Test #26:

score: 16
Accepted
time: 2ms
memory: 81580kb

input:

6 2
1000 1
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1...

output:

1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 

result:

ok correct answer

Subtask #7:

score: 16
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #27:

score: 16
Accepted
time: 59ms
memory: 84244kb

input:

7 195
100000 1000
0 828483622 617711013 242092397 1034026464 456205583 731635466 382894773 533786631 582730039 74863848 661821965 368857719 541353387 662605236 580923280 798012506 54823622 333416217 39292129 995195996 477140985 1014499425 362164396 970752859 879997855 96768859 1005365898 576674982 4...

output:

23456
1000
17
5250 7223 8651 12609 21594 22555 26970 27646 27770 33985 37411 43854 57508 83761 94288 94649 96808 
1 1743 3 20988 1 1 34 4 1 1 1 3 1 1 279 1 393 
17
5250 7223 8651 12609 21594 26970 27646 27770 33985 37411 43854 57508 62999 83761 94288 94649 96808 
1 1743 3 20988 1 34 4 1 1 1 3 1 1 1 ...

result:

ok correct answer

Test #28:

score: 16
Accepted
time: 57ms
memory: 85136kb

input:

7 228
100000 1000
0 230727359 951312015 741711018 367230626 775024687 130794976 435788836 781961691 736694220 427610697 1016199868 798240399 340962994 1006804448 708169239 976753368 364431996 495851435 246658001 190094424 1054346726 639713727 218794912 229693460 313349630 85091951 418997497 27345904...

output:

5906
1000
18
18000 26070 27090 31031 36690 49706 52983 57045 57375 60712 63184 67455 67985 75071 94039 97479 97656 99233 
1 1 1 2 71 1 1 1 2 11 28 3 4034 1 20 1071 656 1 
18
9580 18000 26070 27090 31031 36690 49706 57045 57375 60712 63184 67455 67985 75071 94039 97479 97656 99233 
1 1 1 1 2 71 1 1 2...

result:

ok correct answer

Test #29:

score: 16
Accepted
time: 49ms
memory: 85524kb

input:

7 221
100000 1000
0 716795222 632538294 1008333912 248043863 1023411987 11954597 917179098 100756831 19780613 336926235 768679016 371044675 360783184 402042708 1056697208 567354265 284551620 146863144 1008241012 536649321 680142584 506474136 80860918 973856876 30288601 668537691 877380398 131785980 ...

output:

13893
1000
15
8817 12957 16017 23446 31013 45965 49780 53134 68169 70942 82418 86486 88194 90245 94588 
307 22 1 1 10 1 2415 1 2 1 33 1 1 1 11096 
15
8817 12957 16017 23446 31013 49780 53134 68169 70308 70942 82418 86486 88194 90245 94588 
307 22 1 1 10 2415 1 2 1 1 33 1 1 1 11096 
15
8817 12957 160...

result:

ok correct answer

Test #30:

score: 16
Accepted
time: 10ms
memory: 81748kb

input:

7 1000
3 10
0 729041606 776089922
3 10
0 73695624 783752411
3 10
0 820372959 215264354
3 10
0 919645823 161862972
3 10
0 416211733 881194269
3 10
0 275811209 281074929
3 10
0 582815620 342763006
3 10
0 922520113 399127881
3 10
0 299636294 328307001
3 10
0 666654277 503934330
3 10
0 2735358 732598564...

output:

47048316
10
2
1 2 
33554432 13493884 
2
1 2 
33554434 13493882 
2
1 2 
33554496 13493820 
2
1 2 
33554498 13493818 
2
1 2 
33554688 13493628 
2
1 2 
33554690 13493626 
2
1 2 
33554752 13493564 
2
1 2 
33554754 13493562 
2
1 2 
33558528 13489788 
2
1 2 
33558530 13489786 
710056787
10
2
1 2 
13421772...

result:

ok correct answer

Test #31:

score: 16
Accepted
time: 15ms
memory: 81740kb

input:

7 2000
3 5
0 3978360 573616453
3 5
0 547375641 97549509
3 5
0 710402134 567209414
3 5
0 712013879 1031360933
3 5
0 118351677 538884285
3 5
0 96665729 441728559
3 5
0 1021357084 735021028
3 5
0 882151625 958055123
3 5
0 521548745 517316479
3 5
0 162247430 426447555
3 5
0 423460219 408674001
3 5
0 247...

output:

569638093
5
2
1 2 
33554432 536083661 
2
1 2 
33554433 536083660 
2
1 2 
33554436 536083657 
2
1 2 
33554437 536083656 
2
1 2 
33554496 536083597 
449826132
5
2
1 3 
8388608 441437524 
2
1 3 
8388609 441437523 
2
1 3 
8388616 441437516 
2
1 3 
8388617 441437515 
2
1 3 
8388624 441437508 
143192720
5...

result:

ok correct answer

Test #32:

score: 16
Accepted
time: 6ms
memory: 81744kb

input:

7 1000
4 10
0 827032080 596299879 377757837
4 10
0 139678996 620475310 982977750
4 10
0 327504523 973136882 1056046317
4 10
0 703538140 645917988 869157682
4 10
0 453817111 255127787 753233051
4 10
0 503195344 905031432 746786602
4 10
0 615183881 988518844 555461556
4 10
0 932813811 356392410 858830...

output:

28167702
10
3
1 2 3 
8388608 11828720 7950374 
3
1 2 3 
8388608 11828721 7950373 
3
1 2 3 
8388609 11828720 7950373 
3
1 2 3 
8388608 11828724 7950370 
3
1 2 3 
8388608 11828725 7950369 
3
1 2 3 
8388609 11828724 7950369 
3
1 2 3 
8388612 11828720 7950370 
3
1 2 3 
8388612 11828721 7950369 
3
1 2 3 ...

result:

ok correct answer

Test #33:

score: 16
Accepted
time: 37ms
memory: 83624kb

input:

7 2
100000 1
0 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823 1073741823...

output:

1073741823
1
1
1 
1073741823 
1073741823
1
1
1 
1073741823 

result:

ok correct answer

Test #34:

score: 16
Accepted
time: 44ms
memory: 83704kb

input:

7 204
100000 1000
0 867143449 289720871 62880653 256495758 373546157 114942061 524281177 164218453 261500635 241690011 911469619 794136322 460604293 201667773 1001245336 873383805 136426866 731765422 1036091702 428463064 474020221 916532901 913755707 704796468 745115429 387268771 611877390 101588067...

output:

1241
1000
11
7982 17864 17963 47178 55333 66676 69260 72308 84132 87997 98425 
1 1 132 11 1 119 1 970 1 1 3 
11
7982 17864 17963 47178 55333 57921 66676 69260 72308 87997 98425 
1 1 132 11 1 1 119 1 970 1 3 
11
7982 17864 17963 47178 54490 55333 66676 69260 72308 87997 98425 
1 1 132 11 1 1 119 1 97...

result:

ok correct answer

Subtask #8:

score: 0
Wrong Answer

Dependency #7:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #1:

100%
Accepted

Test #35:

score: 8
Accepted
time: 57ms
memory: 85008kb

input:

8 259
99999 1000
0 184042404 114860590 81955939 149152356 141033215 259145072 144981065 194732174 87943638 3239431 196977178 27923106 209711053 259763893 143914852 152580789 5161376 220134523 49139129 179593854 115442954 268238166 42599190 6509126 76156465 153820967 111093283 89981466 186373935 6842...

output:

553
1000
13
6 28126 34079 36018 36495 37309 49890 54435 74258 74516 76282 77278 89972 
1 253 1 1 1 1 1 1 1 11 1 1 279 
13
6 17070 28126 34079 36018 37309 49890 54435 74258 74516 76282 77278 89972 
1 1 253 1 1 1 1 1 1 11 1 1 279 
13
6 28126 34079 36018 37309 49890 54435 57886 74258 74516 76282 77278 ...

result:

ok correct answer

Test #36:

score: 8
Accepted
time: 11ms
memory: 81616kb

input:

8 2000
4 5
775795058 434974743 31074946 428696702
4 5
373180095 760380481 419902862 1049258222
4 5
667161035 673656536 537091509 513688618
4 5
724027945 494292286 644201747 822331951
4 5
661539617 30050732 358848696 134411535
4 5
385734187 236947885 562514730 169874287
4 5
600384888 205880481 862584...

output:

260593779
5
3
1 2 3 
29511310 127939687 103142782 
3
1 2 3 
29511312 127939685 103142782 
3
1 2 3 
29511310 127939685 103142784 
3
1 2 3 
29511314 127939683 103142782 
3
1 2 3 
29511316 127939681 103142782 
56241154
5
3
2 3 4 
46910078 1624690 7706386 
3
2 3 4 
46910077 1624690 7706387 
3
2 3 4 
469...

result:

ok correct answer

Test #37:

score: 0
Wrong Answer
time: 11ms
memory: 81740kb

input:

8 1000
5 10
925022554 416509837 681820051 569347404 420577661
5 10
676949322 809105046 710668968 622139077 525882012
5 10
1016024766 383498611 324818602 167492568 583945990
5 10
607262806 436684746 91524379 563713486 399361534
5 10
34445929 59287234 604627291 374306204 356825324
5 10
397715954 64098...

output:

178944881
10
4
2 3 4 5 
19697779 6045805 34632372 118568925 
4
2 3 4 5 
19697779 6045805 34632374 118568923 
4
2 3 4 5 
19697781 6045805 34632372 118568923 
4
2 3 4 5 
19697779 6045807 34632372 118568923 
4
2 3 4 5 
19697779 6045805 34632380 118568917 
4
2 3 4 5 
19697779 6045805 34632382 118568915 ...

result:

wrong answer jury has better answer

Subtask #9:

score: 0
Skipped

Dependency #8:

0%