QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#434727#8787. Unusual Caseucup-team3510#AC ✓1524ms50176kbC++143.6kb2024-06-08 17:10:062024-06-08 17:10:07

Judging History

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

  • [2024-06-08 17:10:07]
  • 评测
  • 测评结果:AC
  • 用时:1524ms
  • 内存:50176kb
  • [2024-06-08 17:10:06]
  • 提交

answer

#include<iostream>
#include<random>
#include<algorithm>
#include<unordered_map>
using namespace std;
mt19937 Rand(20080704);
#define rand Rand
struct treap
{
	int l,r,size,fa;
};
treap a[80010];
inline void update(int p)
{
	a[p].size=a[a[p].l].size+a[a[p].r].size+1;
	a[a[a[p].l].fa=a[a[p].r].fa=p].fa=0;
}
int merge(int x,int y)
{
	if(!x||!y)
	{
		return x+y;
	}
	if(rand()%(a[x].size+a[y].size)<a[x].size)
	{
		a[x].r=merge(a[x].r,y);
		update(x);
		return x;
	}
	a[y].l=merge(x,a[y].l);
	update(y);
	return y;
}
inline pair<int,int> query(int p)
{
	int S=a[a[p].l].size+1;
	while(a[p].fa)
	{
		int P=a[p].fa;
		S+=(a[P].r==p)*
		(a[a[P].l].size+1);
		p=P;
	}
	return {p,S};
}
void split(int p,int v,int &x,int &y)
{
	if(!p)
	{
		x=y=0;
		return;
	}
	int sizel=a[a[p].l].size;
	v<=sizel?(y=p,split(a[p].l,v,x,a[p].l))
	:(x=p,split(a[p].r,v-sizel-1,a[p].r,y));
	update(p);
}
int n,m,k,X[200010],Y[200010];
int in[8][10010],out[8][10010];
int ine[8][10010],oute[8][10010];
vector<pair<int,int> > ein[10010],eout[10010];
vector<pair<pair<int,int>,int> > e;
bool mark[200010];
unordered_map<int,bool> E[10010];
int cnt[8];
vector<int> p;
inline bool judge(int x,int y)
{
	pair<int,int> p=query(x),q=query(y);
	return p.first!=q.first||p.second>q.second;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		cin>>X[i]>>Y[i];
		ein[Y[i]].push_back({X[i],i});
		ein[X[i]].push_back({Y[i],i});
		eout[X[i]].push_back({Y[i],i});
		eout[Y[i]].push_back({X[i],i});
		E[X[i]][Y[i]]=E[Y[i]][X[i]]=1;
	}
	for(int i=0;i<k;i++)
	{
		p.emplace_back(i);
		for(int j=1;j<=n;j++)
		{
			a[i*n+j].size=1;
		}
	}
	while(!p.empty())
	{
		shuffle(p.begin(),p.end(),rand);
		e.clear();
		for(int i=1;i<=n;i++)
		{
			bool fin=0,fout=0;
			for(int j=p.size()-1;j<p.size();j++)
			{
				fin|=!in[p[j]][i];
				fout|=!out[p[j]][i];
			}
			if(fin)
			{
				for(int j=0;j<ein[i].size();j++)
				{
					if(mark[ein[i][j].second])
					{
						continue;
					}
					e.push_back({{ein[i][j].first,i}
					,ein[i][j].second});
				}
			}
			if(fout)
			{
				for(int j=0;j<eout[i].size();j++)
				{
					if(mark[eout[i][j].second])
					{
						continue;
					}
					e.push_back({{i,eout[i][j].first}
					,eout[i][j].second});
				}
			}
		}
		shuffle(e.begin(),e.end(),rand);
		for(int i=0;i<e.size();i++)
		{
			if(mark[e[i].second])
			{
				continue;
			}
			int x=e[i].first.first;
			int y=e[i].first.second;
			for(int J=p.size()-1;J>=0;J--)
			{
				int j=p[J];
				if((in[j][y]&&out[j][x])
				||!judge(j*n+y,j*n+x))
				{
					continue;
				}
				if(!in[j][y]&&!out[j][x])
				{
					if((++cnt[j])==n-1)
					{
						p.erase(p.begin()+J);
					}
				}
				if(in[j][y])
				{
					pair<int,int> t=query(j*n+y);
					int X,Y;
					split(t.first,t.second-1,X,Y);
					out[j][in[j][y]]=mark[ine[j][y]]=0;
				}
				else if(out[j][x])
				{
					pair<int,int> t=query(j*n+x);
					int X,Y;
					split(t.first,t.second,X,Y);
					in[j][out[j][x]]=mark[oute[j][x]]=0;
				}
				pair<int,int> X=query(j*n+x),Y=query(j*n+y);
				merge(X.first,Y.first);
				in[j][y]=x,out[j][x]=y;
				ine[j][y]=oute[j][x]=e[i].second;
				mark[e[i].second]=1;
				break;
			}
		}
	}
	bool flag=1;
	for(int i=0;i<k;i++)
	{
		int p;
		for(int j=1;j<=n;j++)
		{
			if(!in[i][j])
			{
				p=j;
				break;
			}
		}
		for(int j=1,last;j<=n;j++)
		{
			cout<<p<<" ";
			if(j>1)
			{
				flag&=E[last][p];
				E[last][p]=E[p][last]=0;
			}
			last=p,p=out[i][p];
		}
		cout<<endl;
	}
	cerr<<flag<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8292kb

input:

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

output:

2 4 3 5 1 
2 5 4 1 3 

result:

ok OK (n = 5, m = 9)

Test #2:

score: 0
Accepted
time: 1519ms
memory: 48508kb

input:

10000 200000 8
6318 9948
9588 8985
4252 4927
1146 9347
2276 7434
9612 4436
8319 1837
4428 1043
5976 2759
879 1564
7866 4849
2070 5310
8407 156
7306 7766
9100 1576
1181 6122
7790 7065
3235 8877
5661 9718
1555 743
5479 9755
2601 8190
3318 2067
4084 8193
1050 269
64 5504
3416 5041
7169 197
2158 2523
57...

output:

2133 334 8992 2008 6967 9059 5110 3530 1972 8842 5892 920 3040 283 7853 3403 6458 2693 9588 713 391 1228 6354 705 1957 7514 8256 4982 1050 7914 9670 8599 1839 7567 8101 2641 3647 7559 896 2725 4375 7557 3927 1207 1270 7674 5771 7809 9132 1083 7517 8472 7237 3813 5047 3510 1027 9562 313 9607 9149 303...

result:

ok OK (n = 10000, m = 200000)

Test #3:

score: 0
Accepted
time: 1353ms
memory: 48524kb

input:

10000 200000 8
7826 9720
8400 2487
6964 6011
4799 6032
3696 3691
7883 4350
9092 3892
3588 7409
6005 4538
4196 7873
4216 4505
6339 1269
2405 5423
9 7030
8193 7285
5782 2768
5646 4946
4483 6857
3431 9325
4243 488
2435 8371
3067 1462
8592 4932
8581 3147
1394 6751
2499 4977
4806 1190
9652 5059
4075 3454...

output:

962 7952 8131 245 9320 9637 2224 8685 8523 6741 7026 6998 3812 8509 3948 8909 2947 2185 9942 5256 1223 7712 2208 3597 7572 5259 4704 3543 3197 9797 1831 5181 4622 9894 8596 4065 6804 3871 8972 8561 4872 3265 9640 5715 9431 5327 9484 4551 5477 4057 4134 1537 8829 5771 6996 4116 9325 897 7087 6144 264...

result:

ok OK (n = 10000, m = 200000)

Test #4:

score: 0
Accepted
time: 1313ms
memory: 48948kb

input:

10000 200000 8
6064 4200
2244 5165
648 6303
9246 8103
4187 7801
761 3539
6105 2254
4471 3158
6006 4452
3580 8120
9391 3711
8752 1014
2511 151
800 2285
5388 3282
4704 8712
5372 5509
6988 6976
9314 9056
2225 9256
8567 3853
4135 3386
9688 1467
7287 5856
8107 7114
2385 3663
2991 2969
3746 7352
8828 6735...

output:

4673 426 5599 8201 171 7288 7339 6684 9561 8191 9576 3683 996 3348 7190 9908 9555 8876 755 1818 7968 4222 4341 9533 68 7430 2597 1016 9051 5593 181 3279 5714 1217 8268 9668 9327 3483 2058 814 2236 4376 1183 332 3146 2563 3833 8360 2412 8455 1307 5941 4974 2785 478 1844 4017 9455 5768 6281 7169 8479 ...

result:

ok OK (n = 10000, m = 200000)

Test #5:

score: 0
Accepted
time: 1524ms
memory: 49996kb

input:

10000 200000 8
1034 3387
1120 7020
5302 5802
4487 5560
3749 9763
8246 2002
9358 6922
7077 8289
5976 2501
9030 2306
3390 2468
9307 4546
8724 4342
9679 3531
684 9564
7946 3956
6968 8754
748 9234
3310 8909
5500 7046
3874 6201
5806 3962
6604 1672
203 6318
1189 1358
9723 1561
7970 380
9450 7078
6420 2366...

output:

7924 1891 3666 5377 158 7354 8705 1345 206 56 548 8678 2709 4617 2310 3223 814 3173 9002 7844 9541 8100 3968 2860 8342 3874 6648 1389 34 846 3076 4997 3196 9627 2415 4917 8742 5582 2226 9103 2210 5284 2305 671 1529 2731 400 4205 2775 605 5397 6912 8057 489 3590 4219 6524 2827 8056 9647 4312 8108 558...

result:

ok OK (n = 10000, m = 200000)

Test #6:

score: 0
Accepted
time: 1373ms
memory: 49480kb

input:

10000 200000 8
2734 7281
5027 8050
927 4507
523 8404
2382 9578
337 9740
8851 7897
1407 2803
5918 8684
547 430
6215 775
8004 1864
1045 7995
6645 767
4082 6133
5510 8499
433 4681
5763 3631
5419 8885
4068 3859
8356 5416
8078 3190
9342 5547
7329 4533
639 9483
4511 8673
9744 3422
6765 4236
6849 346
2288 ...

output:

3989 6185 4070 422 2107 1067 7357 1129 6747 9173 6205 9218 5934 469 5738 3105 8989 7992 9840 1721 9990 2395 2365 4161 9094 9531 4745 5749 1482 952 8606 5007 5408 4654 6915 3032 7472 3940 2257 9670 9299 2942 2040 3492 6538 2030 8154 7152 9808 4264 5301 2644 329 6110 5955 6118 5728 2009 1779 8579 5448...

result:

ok OK (n = 10000, m = 200000)

Test #7:

score: 0
Accepted
time: 1366ms
memory: 48208kb

input:

10000 200000 8
1166 5882
3966 8257
7523 2420
7353 6633
87 7247
7035 6751
4585 5179
7460 6699
5829 3002
8131 2493
7864 8632
4845 2969
9472 1110
1698 3993
5582 2988
7395 2341
5768 3290
2034 167
5642 8983
7929 9694
2014 1497
952 1069
7900 3092
8663 502
6458 1489
6751 4998
8312 2094
5690 8825
115 676
62...

output:

1509 2786 7663 3415 7792 1044 3541 3284 2733 6204 7290 1417 5846 8130 67 3132 9996 5183 2416 6056 3262 2585 8652 2679 2095 3030 9998 4765 2443 3091 4971 3029 9398 4815 5410 1473 7108 407 2890 321 5781 1014 4775 7162 5845 5263 9639 6870 6998 353 750 6356 1725 189 6116 5417 3996 7591 8468 6597 547 498...

result:

ok OK (n = 10000, m = 200000)

Test #8:

score: 0
Accepted
time: 1268ms
memory: 47544kb

input:

10000 200000 8
6328 9191
7937 7640
5090 9539
4977 248
6863 2768
8341 3037
6559 8768
5237 9978
5712 5454
1782 8494
8338 6040
9828 7861
4008 3687
4839 3210
5183 130
3601 5482
2972 4581
9560 8842
3978 9205
7084 4551
4847 4445
4428 7601
2280 4306
4207 4225
8646 7376
6443 536
3674 6398
6226 847
6219 3356...

output:

7502 5400 8158 8907 6119 816 7417 1453 2794 1996 309 4293 1421 5259 5998 9399 7679 4828 4775 1680 5618 9174 4754 660 2393 9164 2250 9016 5119 4453 9774 7161 3181 9766 8284 3459 369 340 3339 9635 469 5157 7941 9030 8807 4605 9334 1972 5656 8852 6244 1225 7825 6045 5626 5423 3087 744 8724 6747 2027 28...

result:

ok OK (n = 10000, m = 200000)

Test #9:

score: 0
Accepted
time: 1321ms
memory: 49708kb

input:

10000 200000 8
8222 7206
6939 6199
3627 5866
3396 9250
2710 6141
4253 8597
4773 8663
4738 2640
5564 6042
1500 8433
7637 2998
2954 6540
4650 5727
6068 8417
2885 7557
4129 7922
2046 8554
8343 9655
428 9550
1531 8431
6855 4259
8506 2784
2481 9190
3961 5701
7203 7144
3585 5286
5830 6332
8372 300
5160 83...

output:

8929 7557 7093 6176 5338 6791 9451 9041 3825 381 2870 2513 4231 2398 3609 8559 6897 9976 9172 6876 1440 8383 1586 6445 427 1985 9823 8864 9178 520 3598 745 9513 8647 4018 4159 35 4089 5503 9119 8450 9745 7034 5486 8337 3893 1524 6390 4790 9672 7475 6489 9900 776 9787 7238 3038 2886 7740 1784 6451 18...

result:

ok OK (n = 10000, m = 200000)

Test #10:

score: 0
Accepted
time: 1300ms
memory: 48888kb

input:

10000 200000 8
6846 9929
974 3935
3136 1399
2610 3637
7628 7368
4772 3431
9227 4865
5962 4684
5388 4763
7285 2311
5760 9506
4223 9005
1401 7229
5384 9615
8690 5272
8977 9661
2990 5210
8380 2608
4990 18
1272 1334
8039 940
3186 6620
8503 7744
7924 4930
2128 794
8179 9250
4781 1898
2129 7185
6939 5764
...

output:

3759 6924 9496 254 4193 3379 7333 100 6635 5366 2335 8851 7056 8691 462 8216 1741 2213 1699 795 8061 906 1180 6807 1874 1407 7104 8143 8097 9060 1542 3266 7381 5181 3014 4996 4402 4113 4278 1511 4252 7233 3480 4195 1529 1459 9685 9680 5937 2795 2886 642 7228 1001 521 14 1143 7450 5809 774 3866 9803 ...

result:

ok OK (n = 10000, m = 200000)

Test #11:

score: 0
Accepted
time: 1356ms
memory: 49164kb

input:

10000 200000 8
2202 7359
40 846
3615 6140
2618 3411
1618 6447
9897 7539
9921 7374
8909 6111
5182 1620
9136 127
2709 5565
3635 5257
4258 8192
2787 6804
2596 3272
8146 700
5803 4547
9673 7699
7666 608
6306 3259
8398 4487
8468 9107
347 9968
6096 1913
3422 8324
225 2426
526 3095
7496 1502
1556 5493
1173...

output:

9212 660 8622 9034 1829 9882 3381 8006 5074 823 1182 4351 1526 4098 37 9328 7354 8551 4240 9727 9147 3421 2008 6949 35 1355 771 9839 6912 8649 2859 5716 4185 160 7140 3352 7122 8918 6326 8078 9726 1291 3 6252 9676 753 2978 7357 2753 7469 2804 334 7513 8572 1035 9053 346 1866 3094 4626 446 3116 7322 ...

result:

ok OK (n = 10000, m = 200000)

Test #12:

score: 0
Accepted
time: 1305ms
memory: 48296kb

input:

10000 200000 8
4288 9496
4137 6934
5065 87
3420 8570
4679 3379
9630 921
6856 6189
3580 6921
4946 6611
7054 1882
8482 1173
1189 5296
3223 8618
8278 9983
4603 1559
1637 1037
487 6567
2222 4930
8456 1322
6633 4206
7932 4900
4352 246
8011 5862
8478 6650
1085 9736
9721 4816
3066 9922
4474 3251
9010 7571
...

output:

7153 8107 9906 3102 1462 4509 7016 8304 4070 9235 1498 3849 382 7626 1698 7959 928 7058 5287 1244 1750 3499 8507 3301 8218 557 4104 9627 4013 5295 8206 1912 4343 8600 9881 9637 2034 7525 7580 4571 993 6344 7338 4767 8490 8433 5291 5480 2211 236 9317 5281 8949 886 79 5311 2106 3993 2694 1529 2003 952...

result:

ok OK (n = 10000, m = 200000)

Test #13:

score: 0
Accepted
time: 1205ms
memory: 49440kb

input:

10000 200000 8
3105 6341
3267 2198
7486 3241
5017 9116
6811 8164
3970 3578
30 1311
9975 7113
4681 9737
1039 7576
3081 6333
6886 9121
8295 8507
1857 9152
4712 132
9449 674
7039 1268
6027 4299
7358 2158
2254 4176
6642 2180
838 38
1497 5426
5069 9140
5117 5029
6669 6418
2399 2381
3063 2432
9302 1999
61...

output:

9949 3896 4244 9662 1587 4249 1086 2794 4865 1660 1761 6602 2540 8566 8492 9935 1598 1534 7793 2779 1573 4950 7244 1186 6314 9551 5533 2751 9754 1953 5895 6183 647 3100 4324 9787 3869 5997 7661 9710 8781 2489 1159 7198 1757 1064 9490 8697 7360 5951 3387 1971 4511 7028 331 337 6064 5818 3310 5803 641...

result:

ok OK (n = 10000, m = 200000)

Test #14:

score: 0
Accepted
time: 1334ms
memory: 49160kb

input:

10000 200000 8
8654 7892
7428 6639
878 5603
7408 5048
8014 802
2916 5509
9445 2740
8092 6688
4386 998
1091 7207
6504 1042
726 6733
9475 7857
3523 4312
2923 8991
1582 9609
5462 8652
1087 5808
4374 3117
3167 3169
4526 6326
7925 8481
804 8660
5869 9384
5517 4202
1069 7233
8527 470
3262 9045
2431 8777
5...

output:

1307 4629 2301 2525 632 8464 9871 5153 5700 7954 137 1017 6857 9065 775 4836 3717 4394 4910 9567 7747 9485 2202 2818 4335 4309 4592 7956 3072 6891 2364 3745 5768 8157 2017 7305 7446 7320 1242 9326 2722 7327 9138 3083 3612 8331 4032 1793 791 3794 312 8941 3128 4673 2727 2921 3374 8316 9030 3208 8378 ...

result:

ok OK (n = 10000, m = 200000)

Test #15:

score: 0
Accepted
time: 1212ms
memory: 49032kb

input:

10000 200000 8
933 4151
6621 255
5240 7171
594 6365
8289 1293
6469 6714
5100 476
7934 5646
4062 393
7210 778
8752 5302
2709 8132
6762 6670
3277 5462
9235 8137
8036 7844
5754 8718
7402 9455
9503 4199
9374 1184
1587 7339
5615 5576
5932 5563
879 7381
2286 7257
2919 7262
1450 4191
5071 3090
8398 7904
28...

output:

6247 7955 315 9580 526 9009 5430 1953 1183 4804 5828 9367 5318 1041 7203 9023 3051 9668 8285 5836 4582 2196 5285 7834 1886 2038 9276 1285 9785 5286 7036 692 2066 9554 104 1105 7064 1019 8876 819 8213 8406 6404 6732 4957 5809 220 7867 4099 5155 3207 4937 7067 1534 1045 6502 2206 2657 1714 2021 8334 2...

result:

ok OK (n = 10000, m = 200000)

Test #16:

score: 0
Accepted
time: 1350ms
memory: 50176kb

input:

10000 200000 8
9943 5117
846 3048
573 7946
4574 3069
7634 9636
4629 7193
6995 4518
9499 3986
3709 7923
9395 8286
9824 9113
2834 3317
156 4944
1118 2603
3649 7569
8811 5378
7915 1466
4973 5241
2746 5405
874 8222
7822 5218
3907 1322
6881 6137
98 3131
5423 4193
2221 6503
1167 3542
8491 4566
7202 9381
8...

output:

7169 6562 1911 663 3059 7804 6542 90 4302 5815 1542 8423 2258 2489 3312 4744 267 1832 1189 7964 1211 9300 7876 5514 4156 5395 3645 9613 6922 6392 2452 2082 5346 7449 4936 3887 460 2410 320 130 147 4580 7753 8284 5070 6540 7408 1477 401 9643 5264 6697 1978 4950 8833 8710 8502 1252 433 2035 4322 5585 ...

result:

ok OK (n = 10000, m = 200000)

Test #17:

score: 0
Accepted
time: 1197ms
memory: 50052kb

input:

10000 200000 8
5685 790
102 5017
6877 7928
9348 5159
6051 5832
7396 6946
5130 4867
2787 1709
3325 3587
7648 9733
9722 2473
1102 2289
9658 2681
7046 5735
6164 7288
3907 2211
1947 6896
3800 3166
4102 6733
7667 4282
3233 9964
2800 5721
3651 380
3526 6635
4930 5010
8974 4957
7678 8525
3522 3474
8844 320...

output:

8901 7502 7071 9946 5659 302 4664 9851 2516 7137 2522 9077 5389 7424 154 7630 4033 5425 837 3418 2122 3373 6404 871 3795 285 7911 1999 1991 960 9931 1348 7804 2469 6842 8363 5296 4684 9049 3707 5088 306 9150 1441 8843 3349 2488 6526 4040 3771 2108 8215 9996 2228 7329 7632 5883 8701 1262 5330 2289 16...

result:

ok OK (n = 10000, m = 200000)

Test #18:

score: 0
Accepted
time: 1285ms
memory: 49712kb

input:

10000 200000 8
8157 1170
4391 6162
4152 7117
4917 2635
3540 9882
4770 5974
9506 1523
7799 8814
2913 7387
1967 5119
8444 5384
7513 5048
5267 9880
1062 4857
6781 7292
3324 8343
7848 5008
3882 3230
3571 8184
9753 9364
7819 1576
2296 8772
6243 8293
1164 7893
805 9708
3179 2624
983 9138
163 9815
3323 938...

output:

520 2014 9379 6097 2916 3548 6350 3238 5303 9024 9566 1280 7296 5086 4563 4419 3888 5636 118 6311 8056 2320 1653 127 5540 3346 927 8695 6476 9164 6352 2379 7054 8568 8425 299 8270 8479 6103 9458 1114 2460 1275 9786 916 8591 6218 2652 6744 9391 5811 3051 2306 3250 8558 9179 8664 7959 3042 1326 82 684...

result:

ok OK (n = 10000, m = 200000)

Test #19:

score: 0
Accepted
time: 1215ms
memory: 48720kb

input:

10000 200000 8
7360 6258
3711 6484
2398 5513
1280 5497
99 1783
6751 4276
121 4485
4535 5302
2471 9321
2353 4443
5992 7845
2067 1594
6983 6541
3166 9969
5499 7584
7063 3774
5618 5802
5220 5433
1153 9758
7132 3469
1580 55
2393 474
4655 9876
3012 6904
3048 8287
4835 9504
1083 5383
8414 3587
640 7909
12...

output:

4997 2487 2983 3624 9054 4837 376 7290 1262 5592 963 2202 5380 9685 5504 7490 3980 1506 1095 6283 7464 7690 560 6736 4212 8431 4192 2084 9541 8623 6530 942 8969 6285 1317 263 7182 1250 3817 8505 9277 2492 9535 7820 845 685 7438 9669 1123 7914 3745 2967 6760 158 9259 5047 9567 1103 21 6149 6596 3842 ...

result:

ok OK (n = 10000, m = 200000)

Test #20:

score: 0
Accepted
time: 1455ms
memory: 49116kb

input:

10000 200000 8
3294 6053
8062 5981
1615 3116
8438 3745
5730 1538
3338 1852
6977 3755
2994 1173
1999 9389
8805 7705
2364 9857
4763 1926
4807 2665
3357 1072
2320 8161
5122 8504
5259 9278
7813 9775
6849 1454
9805 6597
4517 5400
3093 829
8889 5129
9068 3669
1661 747
3942 5597
7977 7258
8276 4791
794 878...

output:

782 8991 5721 8388 591 5591 2334 1731 1461 1249 4151 5226 9587 5364 1109 5774 7112 8173 2718 2844 2559 4289 2793 2286 5689 433 8228 3445 5970 2571 9495 1942 3609 7684 501 988 8024 5864 3835 94 1463 826 3817 3739 3278 3838 2721 5627 1368 2707 1729 4715 1366 295 1674 5947 3795 6335 5145 936 353 8597 3...

result:

ok OK (n = 10000, m = 200000)

Test #21:

score: 0
Accepted
time: 1229ms
memory: 49960kb

input:

10000 200000 8
5960 554
7446 4655
1802 9926
6390 7380
432 9145
4532 8702
73 9330
3176 6426
1498 7593
1325 4906
7561 1419
5603 6045
8738 8250
1636 8165
7241 9025
7503 2533
6769 5436
1662 6255
658 3274
7771 8747
6629 7611
4394 9835
8944 4052
9334 8187
6642 7088
500 903
1665 4765
9749 3427
3786 2010
29...

output:

6848 1960 1124 5194 4179 5634 5786 3691 6690 3660 8438 9274 1815 3687 6553 4195 2037 8651 349 8469 2806 2099 3110 1125 8758 1086 8110 5452 2051 8430 7020 2513 8185 256 861 3294 3639 5213 2409 9593 8950 2492 4027 7598 7422 5359 7984 4828 6966 2095 5178 2762 4268 5993 4451 2022 3412 9046 9816 7025 275...

result:

ok OK (n = 10000, m = 200000)

Test #22:

score: 0
Accepted
time: 1299ms
memory: 48616kb

input:

10000 200000 8
5356 9763
1861 2505
2960 5943
5137 6400
4205 4606
334 4826
9409 1213
5082 1062
968 3931
9911 6045
1583 2531
4585 3950
8777 3298
8002 1249
265 175
4205 5862
148 4277
6766 4875
2580 5217
1030 9919
7916 6689
6297 7493
4820 6644
3810 458
7992 7311
4510 5422
2148 7902
2832 9495
9616 7585
5...

output:

4574 238 6841 1596 1673 8672 2176 1040 972 4465 6912 8996 9959 8148 4411 7232 3111 4567 5171 4717 3051 4595 5197 1059 8751 2230 2013 2724 6418 9274 2705 3893 6187 2590 4794 280 8405 4227 4630 1096 3545 8689 4704 7052 1087 5073 7534 1579 2158 6855 9111 6904 6542 2322 6075 431 8159 7456 1312 8565 9359...

result:

ok OK (n = 10000, m = 200000)

Test #23:

score: 0
Accepted
time: 1411ms
memory: 48316kb

input:

10000 200000 8
1483 3680
1308 9532
5089 1166
4678 806
7049 7919
742 225
4985 9402
8711 5081
408 8403
4565 1123
4429 3193
1709 5643
4923 7808
2456 324
1389 1611
5228 8489
5397 5799
3126 5633
2616 7282
9582 114
8379 2634
8802 3804
6517 2907
2495 483
5711 1414
5972 9154
9425 6671
7526 2994
8283 5509
64...

output:

9312 6545 991 628 7332 1388 6888 8814 1203 5843 2407 1688 652 5931 6875 8522 5531 3194 7026 9179 4037 7160 5271 7035 7224 6017 2706 8550 6034 1040 9724 3505 5528 4353 4034 9932 6480 8939 8552 8781 1975 5914 440 4404 6732 63 2964 8463 6957 4852 8168 2763 9242 6296 217 5883 4523 8842 9494 2149 989 881...

result:

ok OK (n = 10000, m = 200000)

Test #24:

score: 0
Accepted
time: 1455ms
memory: 48960kb

input:

10000 200000 8
4341 2303
5786 5734
8189 5597
5013 599
8965 9085
5757 4898
6801 3898
4064 8482
9819 1010
5285 139
6101 3406
6977 1121
7176 1780
4997 5389
616 3334
572 416
2516 4
742 8531
765 9471
3427 9332
8017 5445
1909 8766
4035 2839
5389 8262
9798 9399
4884 2098
3496 1070
3830 3926
9787 5783
4993 ...

output:

4034 4380 6941 5015 6155 484 3219 4571 3684 1040 5746 4786 4087 1942 7426 8764 2690 2654 2912 1392 6576 6744 7647 5430 1639 1576 8068 9581 161 8044 8694 5747 1337 386 7553 715 2232 1142 5215 9476 5655 9782 3332 9631 1505 1327 4546 3437 6893 9147 8172 3957 3665 9214 3645 9039 5540 2725 576 5095 3104 ...

result:

ok OK (n = 10000, m = 200000)

Test #25:

score: 0
Accepted
time: 1357ms
memory: 48192kb

input:

10000 200000 8
3930 5634
5297 1113
2260 9235
6143 5777
9951 8103
5378 8844
4858 4701
1141 1266
9200 1752
2072 3094
6597 3169
5537 5214
5626 6444
7944 5343
237 1641
1505 6890
9613 3567
7027 1782
2566 7572
6830 5122
5618 2380
7375 6441
2493 3794
254 1264
1248 4256
4362 1100
1744 2290
4130 8407
1501 86...

output:

3268 3493 7410 3293 7841 3076 4297 9123 6228 7690 3526 9747 1838 5490 1418 620 4251 3837 5702 1484 1470 3867 273 2664 6054 6009 7493 5213 9046 8609 8707 5340 9800 5290 4476 6302 6244 1182 4294 3932 1746 3054 8512 2463 4661 5924 3853 8223 6112 4645 5871 4014 3413 9838 6905 6661 9280 3302 299 1964 426...

result:

ok OK (n = 10000, m = 200000)

Test #26:

score: 0
Accepted
time: 1135ms
memory: 47808kb

input:

10000 200000 8
250 3672
9839 5668
7301 2079
8067 6342
9 4975
9607 2066
9155 1811
9941 3432
8551 629
4925 9987
5919 2483
1940 3439
5 8111
4342 3490
3374 7638
4223 2166
2363 6459
9739 743
1402 4217
6997 4834
4819 1666
9929 4646
6536 3713
3806 7080
7079 7011
5063 5627
2022 6762
1269 8085
1309 3380
5929...

output:

2610 4942 8034 7666 190 8808 3606 1408 8359 2033 7385 5480 3309 6865 8187 2125 4726 9663 8334 4983 3649 1321 9371 3087 4861 258 2951 7483 3560 5844 9563 6585 6219 6425 8897 5173 3827 1892 3190 487 2310 1431 1546 7865 9299 1577 5379 5175 8079 3367 3539 1342 6298 6934 9800 4671 4616 6705 3231 8588 262...

result:

ok OK (n = 10000, m = 200000)

Test #27:

score: 0
Accepted
time: 1426ms
memory: 48432kb

input:

10000 200000 8
3302 6417
9413 9399
3313 4131
786 2293
9139 9699
8443 4561
9691 5227
464 4981
7873 7640
3846 819
4065 1347
1636 278
581 470
1146 6526
6905 220
2531 1990
5091 8710
1122 57
3891 6774
6722 1119
1982 5076
4842 5563
1517 4655
9328 8119
273 6638
6329 6210
6476 8054
2405 1312
1326 703
8278 3...

output:

6061 4597 1106 8846 4755 7938 8698 8188 6167 2427 7003 3358 7999 318 2897 6818 227 3443 8466 9126 9173 8490 711 2782 694 9731 6267 5888 3400 6154 6349 9893 285 4884 8322 5768 4248 8388 3642 9633 4667 4722 9364 5814 7851 3729 7707 6465 9094 6531 9178 5755 3894 6478 6707 2487 7376 5920 4981 9582 9337 ...

result:

ok OK (n = 10000, m = 200000)

Test #28:

score: 0
Accepted
time: 1294ms
memory: 48248kb

input:

10000 200000 8
3084 3869
4018 2306
296 5389
4299 3629
7339 2276
1885 6331
6469 4950
2711 5913
7166 2786
8833 5589
1036 9761
9475 904
7264 2290
6037 5553
8538 3088
5159 1113
9688 3643
3759 1510
4493 9454
1740 6427
8322 5352
357 5133
2320 9267
9060 6912
9835 147
5047 6007
7724 4978
5151 1971
4181 376
...

output:

9343 8476 8516 2217 6768 3782 208 4696 809 4641 9314 9693 4114 8431 6252 5865 2234 5710 422 7252 1289 8277 7783 5703 6230 5356 3303 7865 8566 6098 4425 1652 3221 6639 6904 4266 4644 1420 4848 9367 6987 5539 1829 7083 2660 9621 2610 3064 2557 7760 8470 731 9081 6668 7016 1884 179 1971 4514 3717 150 4...

result:

ok OK (n = 10000, m = 200000)

Test #29:

score: 0
Accepted
time: 1297ms
memory: 49280kb

input:

10000 200000 8
9597 6028
3656 4390
8250 5855
8607 352
4611 2706
9934 7374
9486 979
6681 6227
6429 6067
9887 4297
6831 7725
5456 5316
54 3573
9016 570
8272 6242
2109 9535
6155 1258
7653 5102
3208 2257
2051 757
3836 2495
6474 3355
8945 7549
3001 3458
5766 7537
1216 5016
5767 7532
9508 62
9873 2398
673...

output:

5068 3686 6775 7056 8783 1816 9152 3777 5059 7057 3412 3293 7737 7227 4901 6399 5412 7785 4642 4824 5001 5852 6990 8889 214 1457 1369 6389 4823 3518 8521 279 7980 3824 9368 4292 4200 7186 9692 5811 5028 7429 1881 4482 2027 6132 21 3750 5032 9556 2729 4144 3538 265 8845 140 5372 6051 3136 4622 1259 4...

result:

ok OK (n = 10000, m = 200000)

Test #30:

score: 0
Accepted
time: 1297ms
memory: 48820kb

input:

10000 200000 8
2841 2895
8325 5650
7175 5527
3709 2461
954 989
2590 7692
8743 3316
2375 5924
5663 7482
7008 6944
1452 5240
9580 3515
8952 4318
82 1578
6108 9683
3380 7256
4492 1555
2801 833
37 5183
7656 4109
8526 6505
3193 228
1390 9500
1152 7758
8065 8808
4837 3239
605 5717
5475 5585
8403 6770
2849...

output:

2157 5633 2207 9238 1747 386 6718 9077 6023 6854 3344 6036 5771 867 1728 5813 6090 3712 2826 2724 1918 838 8932 9121 3955 5623 610 287 9526 7082 8343 2766 6667 4377 2012 5263 637 9169 6698 8106 6519 3951 5931 3948 8112 2847 4156 6374 920 8748 7391 1942 9850 7557 8031 4053 3128 8542 4992 9905 9064 44...

result:

ok OK (n = 10000, m = 200000)

Test #31:

score: 0
Accepted
time: 1404ms
memory: 49840kb

input:

10000 200000 8
2816 4469
8026 6086
7071 4407
9605 9956
6368 7125
9853 7284
4241 1959
9793 5004
4867 7032
196 3530
4897 2305
1847 5501
3957 4526
9236 8577
2046 3410
8972 4276
4699 4534
9206 8703
4979 8232
8553 6484
2391 7381
513 5754
9656 5122
3511 9811
6734 3960
5908 674
2236 9534
3053 8540
9771 349...

output:

3014 9853 1618 7585 2824 9423 8556 7301 5721 6533 6719 4318 6677 6288 9454 8398 5017 5328 6012 9999 8333 5221 3361 2606 442 8840 3440 2221 8586 111 4538 3200 6838 5069 8922 8634 3475 4339 5291 9133 5364 1892 6145 5307 8440 1133 7614 8327 4150 8880 9640 7208 5851 121 79 7897 5155 6038 6622 8640 2931 ...

result:

ok OK (n = 10000, m = 200000)

Extra Test:

score: 0
Extra Test Passed