QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #105483 | #6413. Classical Graph Theory Problem | woxiangbaile | AC ✓ | 2398ms | 50504kb | C++14 | 990b | 2023-05-14 09:14:02 | 2023-05-14 09:14:04 |
Judging History
answer
#include<bits/stdc++.h>
#define f(i,x,y) for(int i=x;i<=y;i++)
#define df(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
using namespace std;
const int N=1.1e6;
int n,a[N],a1[N],c[N],l,l1,x,y,cs,t1,m,t,v[N][2];
vector<int>b[N];
mt19937 rd(time(0));
void cg(int i)
{
t-=(!v[i][c[i]^1]);
for(int u:b[i])t-=(!v[u][c[u]^1]),--v[u][c[i]];
c[i]^=1;
t+=(!v[i][c[i]^1]);
for(int u:b[i])++v[u][c[i]],t+=(!v[u][c[u]^1]);
}
signed main()
{
scanf("%lld",&cs);
while(cs--)
{
scanf("%lld%lld",&n,&m);
l=l1=0;
f(i,1,n)b[i].clear(),v[i][0]=v[i][1]=0;
f(i,1,m)scanf("%lld%lld",&x,&y),b[x].pb(y),b[y].pb(x);
f(i,1,n)if(i&1)a1[++l1]=i,c[i]=1;else a[++l]=i,c[i]=0;
f(i,1,n)for(int u:b[i])++v[i][c[u]];
f(i,1,n)t+=(!v[i][c[i]^1]);
while(t)
{
x=rd()%l+1;y=rd()%l1+1;
t1=t;
cg(a[x]),cg(a1[y]);
if(t1<t)cg(a[x]),cg(a1[y]);
else swap(a[x],a1[y]);
}
f(i,1,l)cout<<a[i]<<' ';
cout<<'\n';
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 29196kb
input:
2 6 7 1 2 1 3 2 3 3 4 4 5 4 6 5 6 3 2 1 2 2 3
output:
2 4 6 2
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 93ms
memory: 29468kb
input:
10000 2 1 1 2 29 28 13 19 16 5 21 7 22 10 10 2 1 18 27 13 10 3 11 23 12 22 11 7 7 17 29 17 9 1 28 21 2 18 13 9 4 25 20 16 5 14 20 7 14 4 12 8 8 24 17 19 15 1 11 6 26 9 13 12 13 9 12 2 6 12 9 11 5 2 8 10 6 10 3 10 7 1 7 5 8 9 4 1 12 11 10 6 2 8 12 4 5 10 11 1 3 1 10 1 12 9 9 1 8 3 7 1 35 35 13 8 34 1...
output:
2 27 4 3 17 15 22 14 16 18 20 11 24 9 28 2 5 6 1 10 9 9 4 6 8 5 1 12 4 6 23 10 29 25 20 18 33 1 24 22 28 16 32 21 18 4 3 5 2 12 14 13 16 2 2 4 49 4 43 47 13 12 33 50 29 21 24 9 26 23 42 14 2 37 18 27 5 15 46 48 16 8 4 6 14 29 12 2 34 11 17 22 9 35 28 27 32 25 10 2 11 6 5 10 12 14 13 4 17 ...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 182ms
memory: 29628kb
input:
1000 337 338 164 11 138 75 114 262 170 298 166 241 269 24 9 134 233 60 50 222 231 253 296 242 173 18 93 223 116 151 312 150 82 236 180 20 297 184 268 70 334 162 217 135 258 321 80 209 212 208 18 163 227 104 334 135 77 118 17 230 307 105 307 335 29 24 111 177 324 24 85 3 214 191 310 182 22 171 202 21...
output:
169 4 53 257 323 69 278 16 18 149 235 24 79 275 12 141 40 168 90 289 199 89 217 25 50 253 54 56 58 190 184 73 66 31 70 5 74 76 303 80 201 163 86 120 159 247 162 96 98 176 7 85 245 165 110 146 255 88 19 145 324 48 45 128 114 132 230 136 11 26 142 104 91 191 150 133 154 156 158 160 129 148 279 105 170...
result:
ok ok (1000 test cases)
Test #4:
score: 0
Accepted
time: 304ms
memory: 30456kb
input:
100 1038 1044 206 546 372 853 526 57 777 72 645 866 15 716 254 707 366 753 635 809 850 407 616 149 839 175 320 770 649 686 857 798 1027 40 988 566 315 500 187 615 100 523 867 708 51 381 858 9 177 55 310 54 355 215 78 26 740 570 523 797 828 693 930 981 208 185 663 957 298 523 235 496 622 174 285 247 ...
output:
93 23 771 776 10 490 14 19 1033 926 129 24 305 187 700 675 34 340 74 613 1018 39 247 311 367 52 134 26 58 60 783 601 66 261 969 54 549 76 573 80 849 379 86 88 682 331 1 469 563 100 94 377 879 277 811 112 114 724 118 616 855 1017 126 128 130 132 72 136 138 140 142 360 146 148 818 253 533 229 158 160 ...
result:
ok ok (100 test cases)
Test #5:
score: 0
Accepted
time: 893ms
memory: 35668kb
input:
10 1380 1393 960 647 1319 708 57 1128 751 148 1291 602 835 921 942 406 622 616 967 91 555 545 871 10 447 471 1140 306 149 121 587 165 1179 936 256 787 332 374 729 129 631 481 976 86 1128 1300 477 776 460 313 538 632 1210 275 355 470 1324 885 870 1325 389 979 468 532 41 416 1026 243 1153 152 948 323 ...
output:
180 559 685 8 493 12 1371 16 1118 20 1197 24 26 902 992 32 1175 507 245 40 295 545 321 48 495 764 1246 674 350 407 572 650 1009 496 1054 1101 74 306 1295 635 47 84 1211 887 424 92 94 131 702 100 478 1231 161 739 111 1172 114 875 128 664 998 1045 116 849 35 561 252 136 723 1148 1074 1139 371 148 150 ...
result:
ok ok (10 test cases)
Test #6:
score: 0
Accepted
time: 2398ms
memory: 42936kb
input:
1 200000 201978 69113 28513 94227 164392 56849 195513 22579 149089 195084 193248 121765 162768 135432 101508 107443 89723 12337 87598 173450 107835 13160 161882 18965 179808 53739 23609 114567 23456 195251 178048 61586 87664 179364 25594 90158 169714 30104 161354 143346 4279 177208 87389 122480 1269...
output:
2 63182 142311 62371 14830 12 64794 16 138005 152556 22 24 83918 192784 30 113625 34 36 38 166727 42 44 46 116983 57395 165844 18323 6035 58 54877 32529 94631 149550 72719 54893 72 74 76 37845 80 66571 184202 86 88 105694 33997 116878 96 180027 100 102 178873 167308 14544 130003 40527 184229 108807 ...
result:
ok ok (1 test case)
Test #7:
score: 0
Accepted
time: 84ms
memory: 29508kb
input:
10000 41 44 18 29 38 6 7 4 34 27 40 37 12 40 18 38 11 18 30 39 2 21 10 34 33 2 8 12 30 23 6 2 12 21 15 7 17 1 36 15 31 36 15 21 38 31 1 11 4 30 16 33 19 32 21 30 32 35 1 3 27 9 1 34 11 5 26 25 22 5 34 24 23 32 28 2 20 33 13 15 31 21 38 41 26 3 13 14 14 33 11 11 3 1 9 11 6 3 8 1 7 2 4 3 10 2 9 2 5 4 ...
output:
2 11 33 39 17 12 14 36 37 41 22 21 26 6 31 32 34 4 9 29 2 4 6 8 11 2 4 6 8 10 1 14 16 2 1 25 8 17 33 15 5 18 20 22 29 11 14 30 32 24 2 4 6 8 2 4 2 7 17 8 10 12 14 16 2 7 6 8 7 3 6 8 10 12 14 2 1 3 7 2 4 6 2 4 7 8 2 5 6 4 22 4 16 8 24 7 13 6 25 17 26 5 19 1 5 4 6 1 10 12 3 16 13 21 18 ...
result:
ok ok (10000 test cases)
Test #8:
score: 0
Accepted
time: 69ms
memory: 29212kb
input:
10000 11 13 6 3 9 4 10 4 9 6 10 7 1 5 2 11 2 8 10 6 2 9 6 7 2 5 5 11 3 2 2 1 2 3 2 1 2 1 12 14 12 11 10 7 5 6 2 5 5 8 8 3 8 1 3 12 12 7 2 10 10 11 6 4 11 2 9 3 4 4 1 2 1 3 4 3 2 3 11 13 3 7 1 5 1 6 8 5 9 7 1 2 1 11 2 4 10 9 10 1 7 2 8 3 8 6 2 1 1 2 15 18 3 11 2 10 7 14 14 4 7 3 6 11 15 12 5 11 2 7 7...
output:
2 4 6 1 10 2 2 11 4 7 1 2 3 2 4 3 2 1 5 9 2 2 4 9 5 13 1 11 49 4 44 36 5 1 14 51 61 3 27 40 26 42 7 28 20 17 2 65 30 53 35 48 43 52 32 56 55 60 41 58 59 2 9 12 10 7 11 1 4 6 8 13 3 6 8 21 5 14 29 20 26 7 12 23 28 30 10 9 36 25 37 28 33 8 56 78 19 48 27 20 36 2 55 79 25 44 34 67 46 47 42 ...
result:
ok ok (10000 test cases)
Test #9:
score: 0
Accepted
time: 69ms
memory: 29368kb
input:
10000 10 14 4 9 5 10 1 10 7 6 8 6 9 6 8 3 8 7 4 6 5 3 10 4 10 2 4 8 1 9 6 8 1 2 5 2 5 1 3 4 5 3 6 5 2 3 3 1 3 3 2 1 3 2 3 1 18 26 18 3 10 11 2 4 17 4 8 12 14 15 1 12 13 12 15 7 13 15 14 2 17 5 1 13 11 16 9 3 13 9 6 12 11 14 3 4 3 11 7 11 8 2 8 4 15 6 12 10 12 18 24 35 18 4 22 10 1 21 22 6 23 7 6 14 ...
output:
2 4 6 1 3 2 4 6 2 14 4 8 3 5 12 7 16 13 2 4 3 21 13 23 14 16 18 20 22 24 16 4 6 8 10 12 14 30 15 3 22 55 26 65 31 46 34 54 57 40 42 32 18 48 39 61 36 13 11 60 62 59 20 11 7 6 8 1 12 30 4 7 8 20 29 5 13 24 22 11 28 26 12 14 32 7 9 6 8 2 4 6 8 10 12 11 4 9 8 10 12 14 74 18 20 25 51 7 26 61 3...
result:
ok ok (10000 test cases)
Test #10:
score: 0
Accepted
time: 74ms
memory: 29468kb
input:
10000 4 6 1 3 2 3 4 2 4 1 1 2 4 3 25 51 19 15 19 10 12 3 9 7 5 4 7 21 25 12 20 16 1 13 20 14 15 12 20 13 8 5 16 9 17 13 3 25 25 20 16 22 4 8 5 7 9 10 5 11 4 24 13 21 9 4 15 24 16 11 13 4 22 21 4 14 20 10 12 6 1 4 3 18 9 6 5 2 24 3 16 4 6 16 25 16 21 16 22 25 3 21 10 15 25 23 1 19 7 15 15 20 19 14 17...
output:
2 4 7 4 6 5 10 12 23 16 18 17 22 24 2 4 2 4 7 8 10 12 14 29 18 20 25 24 26 28 23 12 4 6 8 10 23 14 16 31 20 22 17 26 29 30 32 34 36 2 4 15 13 1 12 5 16 17 13 4 31 8 10 14 17 5 18 25 22 9 26 28 23 32 2 4 6 8 10 12 2 4 9 8 10 12 14 2 4 21 27 1 18 20 16 35 5 22 24 9 8 11 19 34 36 10 40 5 4 15...
result:
ok ok (10000 test cases)
Test #11:
score: 0
Accepted
time: 75ms
memory: 29364kb
input:
10000 24 60 13 22 6 12 21 17 24 8 15 11 18 19 17 7 24 1 18 16 21 2 17 12 21 11 10 7 9 18 6 21 17 10 3 24 16 12 7 23 11 8 22 24 3 17 23 3 1 12 8 5 4 24 15 13 8 22 2 8 13 17 10 2 2 7 7 18 18 14 22 20 13 6 5 16 22 23 21 22 5 24 21 14 1 7 12 20 24 20 8 14 17 11 1 19 17 8 9 10 1 11 14 13 10 15 19 11 14 2...
output:
2 4 6 8 10 12 14 16 18 20 22 3 2 4 2 4 30 13 10 3 16 19 18 7 5 14 26 28 17 2 4 6 8 10 12 14 16 18 20 22 2 17 34 8 10 9 14 33 3 35 37 4 31 28 30 39 23 36 42 40 20 24 2 4 6 8 10 12 14 16 18 20 22 24 2 4 6 8 31 12 14 16 9 20 22 24 26 28 11 32 34 36 1 40 21 4 9 8 10 12 14 16 18 20 22 2 26 7 2 4 ...
result:
ok ok (10000 test cases)
Test #12:
score: 0
Accepted
time: 141ms
memory: 29476kb
input:
1000 53 57 47 22 30 20 37 51 19 4 39 22 29 53 1 11 53 18 33 52 29 2 21 50 42 50 42 49 36 44 37 16 5 24 52 35 8 36 28 29 9 24 24 34 32 37 44 46 31 2 13 45 5 21 3 19 17 47 14 35 33 43 43 27 48 13 16 12 33 30 26 14 8 49 41 27 43 45 6 9 36 22 20 37 38 5 17 25 3 7 42 3 33 10 23 50 1 14 40 24 45 42 48 52 ...
output:
2 25 6 23 15 7 14 12 29 44 4 40 27 47 38 32 33 36 21 30 42 51 1 48 34 39 3 4 6 8 10 12 15 39 51 57 47 33 26 52 30 32 44 36 25 13 16 42 46 56 5 41 54 28 58 87 225 247 8 10 81 291 16 79 285 135 159 13 38 261 175 34 36 30 40 257 61 65 48 50 229 54 221 45 259 231 73 193 68 70 213 286 76 112 29 82 84 1...
result:
ok ok (1000 test cases)
Test #13:
score: 0
Accepted
time: 106ms
memory: 29456kb
input:
1000 137 178 124 131 53 109 99 21 107 122 79 28 80 88 126 9 16 1 29 55 126 54 13 39 135 16 63 56 123 121 27 74 81 95 34 38 49 85 127 135 87 106 91 68 57 124 122 113 87 1 52 104 135 93 132 12 98 83 85 26 66 76 41 82 108 90 88 59 29 15 75 58 36 14 116 65 83 64 21 105 132 13 7 70 97 127 92 112 126 55 1...
output:
27 124 6 8 86 54 37 91 132 118 96 128 26 98 78 32 34 114 67 40 42 14 46 48 66 28 69 56 58 60 80 95 68 103 123 72 74 53 111 59 82 84 75 7 108 92 11 93 39 100 102 94 52 71 110 1 44 77 33 16 122 73 126 31 109 113 61 129 2 4 6 29 10 39 14 16 13 27 22 33 26 42 30 32 11 36 45 40 25 15 21 20 50 11 4 38 4...
result:
ok ok (1000 test cases)
Test #14:
score: 0
Accepted
time: 117ms
memory: 29392kb
input:
1000 148 221 51 9 45 80 86 44 133 98 100 25 130 4 99 17 28 44 131 87 103 87 102 53 115 49 9 5 105 130 11 69 56 23 148 106 106 85 57 102 15 147 100 52 22 10 138 60 38 12 126 119 12 125 86 62 108 123 15 63 90 93 35 116 1 75 63 126 23 127 143 127 114 24 12 133 144 82 12 29 6 51 67 26 129 79 115 16 53 6...
output:
104 113 6 38 105 25 145 16 103 20 134 140 26 115 55 67 34 132 133 91 39 44 72 43 137 41 54 56 53 29 131 35 66 49 40 62 74 135 78 32 69 84 45 88 68 92 94 96 98 100 102 82 108 121 125 112 71 114 97 36 122 90 118 79 147 31 15 107 48 14 142 89 60 141 13 4 33 1 36 12 3 9 18 20 22 17 34 28 30 8 16 43 38 ...
result:
ok ok (1000 test cases)
Test #15:
score: 0
Accepted
time: 100ms
memory: 29728kb
input:
1000 527 1061 464 254 106 364 251 82 282 81 152 454 399 114 527 289 430 519 202 320 177 302 398 55 358 181 495 240 86 426 113 171 201 262 82 336 403 77 266 21 176 132 14 97 139 137 479 397 153 403 156 308 105 28 109 272 294 170 336 508 439 105 259 101 429 441 118 200 189 56 297 184 457 385 248 334 4...
output:
2 302 6 8 10 445 188 16 490 20 437 24 26 37 30 32 34 36 15 115 42 44 46 31 50 52 489 483 58 60 62 64 66 182 70 72 187 119 235 351 511 84 137 88 231 519 267 96 98 77 102 104 106 108 296 112 401 116 493 508 122 124 150 128 48 126 134 63 369 140 142 253 146 233 59 152 154 205 240 160 162 164 166 168 17...
result:
ok ok (1000 test cases)
Test #16:
score: 0
Accepted
time: 95ms
memory: 29612kb
input:
1000 24 59 14 16 17 22 19 4 3 21 15 11 4 15 24 6 12 18 15 19 6 17 6 3 19 6 17 18 24 12 3 8 13 8 3 19 22 19 20 18 2 14 16 9 22 15 19 8 22 4 10 7 11 3 22 3 8 12 11 17 24 13 8 21 22 9 13 18 9 12 19 5 10 22 23 3 21 20 4 24 1 15 21 23 18 7 5 22 1 11 22 16 16 24 1 20 20 4 5 23 10 3 7 8 20 9 9 6 23 24 14 9...
output:
2 4 6 8 10 12 3 16 18 20 22 24 2 4 45 89 10 12 14 37 18 20 22 81 27 28 30 32 34 36 38 15 42 44 46 48 50 59 54 56 58 60 62 64 73 68 70 72 97 55 78 105 82 35 93 88 90 92 94 96 98 7 102 104 106 108 13 112 114 116 33 120 79 39 66 2 133 44 8 10 17 406 163 11 220 253 24 328 28 164 240 34 36 225 40 42 11...
result:
ok ok (1000 test cases)
Test #17:
score: 0
Accepted
time: 256ms
memory: 30416kb
input:
100 1400 1550 949 973 216 1089 101 284 568 543 878 648 1125 1117 1052 486 1260 1161 1397 54 1005 922 483 168 202 152 899 685 978 388 1223 1178 1109 239 932 415 105 28 596 251 357 865 842 224 887 1053 304 484 697 780 1164 193 411 798 1267 1395 40 166 21 1027 814 742 905 354 1332 1346 86 1274 726 73 4...
output:
88 742 124 133 10 1309 649 16 18 1150 734 1205 26 719 30 889 34 172 38 87 1301 341 915 48 193 865 54 521 58 1047 697 64 66 574 346 723 754 76 608 979 82 457 2 1158 19 949 1000 1298 98 100 1046 642 177 684 110 1262 794 95 59 1279 1367 389 68 128 130 621 1033 1055 1251 60 290 1207 262 1201 150 1320 31...
result:
ok ok (100 test cases)
Test #18:
score: 0
Accepted
time: 183ms
memory: 30760kb
input:
100 15151 19865 9599 11515 2453 4807 12417 12980 8787 12984 2666 3990 7030 3605 13780 1990 6564 14035 12745 5300 9179 9047 1105 8795 13193 2009 2347 3783 4282 2640 8744 2083 12968 1734 111 1688 14899 11212 11013 15151 4326 6532 9261 10694 8013 10608 8980 9408 379 3570 5827 13496 273 14106 1090 12649...
output:
10147 12882 4346 600 11319 12 10925 4363 1208 20 3732 24 493 28 11912 2002 34 4994 2931 8405 1651 11613 46 11681 12473 8856 3769 6487 6737 7421 8583 64 10019 6915 13103 6481 10900 76 930 4734 82 12479 1297 14252 90 5276 7895 2822 2040 1540 103 104 7008 7785 6534 8373 114 14058 118 5655 8956 1847 911...
result:
ok ok (100 test cases)
Test #19:
score: 0
Accepted
time: 157ms
memory: 30496kb
input:
100 1387 2091 632 868 379 1372 1247 788 72 562 1014 374 677 436 478 1033 997 896 1016 925 291 450 458 392 91 65 380 135 318 757 471 281 390 874 752 953 401 688 978 284 1276 639 565 1356 368 1259 673 639 283 551 647 94 125 1097 1055 672 538 1183 998 813 391 27 1066 766 782 1323 1220 164 427 819 274 5...
output:
1171 1268 161 1124 436 107 1331 668 18 868 669 1369 26 759 754 72 750 47 206 40 609 294 46 48 606 856 229 56 1201 1071 1310 837 190 68 852 794 74 634 1073 1259 1204 1088 1346 88 135 92 345 308 98 1267 237 1216 106 591 312 153 114 777 482 549 741 214 126 1257 987 499 1378 841 242 21 273 1284 1144 201...
result:
ok ok (100 test cases)
Test #20:
score: 0
Accepted
time: 127ms
memory: 30604kb
input:
100 515 1036 358 355 124 512 414 420 214 74 423 447 344 263 431 482 364 446 314 200 299 244 389 507 191 58 85 405 130 57 288 370 231 324 442 405 324 42 453 137 312 167 33 67 443 27 497 101 447 442 211 438 200 210 472 219 462 227 210 19 416 76 483 374 48 374 259 264 331 214 486 213 146 254 264 350 36...
output:
413 309 6 121 228 12 14 16 18 424 441 364 451 484 416 191 115 4 38 293 203 304 110 506 9 306 352 471 42 60 62 64 66 68 335 72 74 347 422 80 28 113 86 480 253 215 359 487 54 358 301 65 186 209 469 300 125 25 488 57 346 91 229 128 130 132 134 55 405 140 142 144 295 148 150 152 154 49 158 160 269 164 1...
result:
ok ok (100 test cases)
Test #21:
score: 0
Accepted
time: 139ms
memory: 30796kb
input:
100 985 2463 916 513 388 126 199 847 456 244 218 236 243 961 588 899 242 137 98 45 273 505 332 492 828 494 368 889 551 617 662 87 651 450 645 884 49 487 731 934 328 482 224 101 590 687 80 972 143 154 420 155 113 886 413 716 841 402 334 374 549 893 62 743 964 386 608 294 124 692 213 980 857 886 228 6...
output:
800 614 192 8 132 437 14 948 368 888 478 828 181 337 30 32 396 36 629 40 702 1 291 237 953 268 54 308 58 521 187 609 854 68 494 205 748 311 872 80 82 176 239 711 873 347 950 863 281 421 285 481 106 909 303 642 352 524 118 62 209 16 498 241 194 528 331 896 138 140 33 699 397 869 496 152 94 527 575 16...
result:
ok ok (100 test cases)
Test #22:
score: 0
Accepted
time: 517ms
memory: 35232kb
input:
10 6620 7333 1646 5207 3808 6296 3890 1170 841 4461 3269 5613 3427 743 4429 351 6077 6488 1639 2661 704 600 1959 6216 4631 689 62 659 1849 1253 2888 6071 823 3326 4491 1670 4620 1541 2403 1275 5905 998 6515 5675 5204 2518 2 6397 5388 5626 1712 3996 6069 3525 962 4452 5528 5749 5292 1334 4864 4469 21...
output:
6476 5951 4835 4519 3981 3318 1686 1558 1964 52 22 4996 1449 5295 3769 4386 5365 1253 2080 1913 42 44 46 2599 1657 5829 448 2986 2071 5802 62 2707 886 6294 70 3564 697 76 78 5134 6281 84 2396 2854 4716 92 94 3496 3132 2520 102 2598 4627 2493 110 4018 2349 116 118 703 122 524 126 5133 1927 447 2551 4...
result:
ok ok (10 test cases)
Test #23:
score: 0
Accepted
time: 379ms
memory: 34856kb
input:
10 31631 41405 12464 26816 7161 23441 26603 26999 3101 17725 19057 12144 25877 18100 27212 15122 23942 15607 10953 6392 8135 30928 10824 21016 16740 16082 31166 11527 30093 3178 18953 11904 16873 18594 31034 21707 18284 11028 10289 6972 4229 16452 6726 8826 15758 31430 30272 23869 31004 31424 15626 ...
output:
2 16444 8800 8 7699 12 2009 16 16585 6387 30338 24 2747 20152 5623 25604 12709 36 5846 40 21263 13891 14552 29574 50 25758 5918 29392 6251 19223 1095 18510 27309 9596 30461 26858 28321 76 18365 30917 2958 9310 20653 88 20126 24059 1910 96 11253 19687 31140 18744 25658 14191 17297 29431 765 30919 118...
result:
ok ok (10 test cases)
Test #24:
score: 0
Accepted
time: 282ms
memory: 34728kb
input:
10 28538 43099 13200 13914 26716 18327 28186 28518 1215 11877 11167 9447 24145 13428 13894 1222 12303 4558 7451 3511 24131 6746 3501 5306 13827 16899 19501 15623 18276 4006 16371 3015 3638 27140 3419 28191 649 11619 7330 19380 3215 17183 13519 12575 3643 1100 23996 5666 7650 3931 11863 18905 11099 2...
output:
26767 6761 27284 16935 10 12 266 16 11486 28254 7259 24 26 21643 30 16697 6955 15030 17280 25755 1227 8037 22951 22934 50 7504 15586 10037 6651 18475 5322 21194 66 68 10369 17849 22508 76 23457 80 15025 5527 8595 4809 14248 7572 12592 96 7839 1972 102 16101 106 108 3751 21331 4453 17766 11883 11143 ...
result:
ok ok (10 test cases)
Test #25:
score: 0
Accepted
time: 308ms
memory: 38560kb
input:
10 87788 176493 85411 2449 75677 87148 41863 8856 26947 41851 69142 52475 19624 254 68187 45850 1914 1328 60252 34269 74977 29820 84340 25888 15811 3705 1188 51146 923 7500 4632 78262 79717 73522 51839 29805 50741 81652 34291 1102 47663 68963 8687 86118 17441 86354 11708 6564 87269 85939 81969 15769...
output:
67890 80873 957 8 10 50250 63145 71073 52270 20 39409 60053 60790 54553 78447 68703 36652 46821 46586 77980 56887 21584 46 11743 54782 16391 27991 50979 58 60 54475 4535 83475 50921 23306 33596 60015 76 48710 66347 67179 84 58187 59822 77760 75065 43892 15207 4741 83231 70702 14142 26122 108 83384 1...
result:
ok ok (10 test cases)
Test #26:
score: 0
Accepted
time: 230ms
memory: 34528kb
input:
10 8816 22043 7419 5025 5365 4666 3322 7417 5863 5973 2641 1448 6401 2157 1667 7379 6833 7402 5527 5022 2651 4669 4676 5212 3876 2581 5037 6774 2606 6661 5930 519 3836 8394 1159 3510 2789 2327 5496 4249 5240 4702 4006 7011 5102 1260 2708 1364 8618 888 3465 3208 5175 3282 5081 6716 5593 1814 2896 663...
output:
2 7606 8281 5497 8310 5495 162 16 8779 933 7991 3247 3931 8493 2102 4309 4245 3308 804 1668 5700 2324 723 701 1981 5294 8688 7191 8379 60 3035 1112 489 5368 70 8350 3823 5422 5701 80 8749 6762 119 2967 784 4227 204 2622 2321 8467 2945 8775 7777 8153 8261 457 114 116 4575 3799 479 7355 345 4705 6294 ...
result:
ok ok (10 test cases)
Test #27:
score: 0
Accepted
time: 1290ms
memory: 43300kb
input:
1 200000 222059 53595 110970 173632 131224 18782 129709 79934 195396 42423 87939 191850 58500 75657 76504 130760 155268 40793 74463 110561 181427 166061 166730 169476 19173 54038 80930 98140 20017 131017 7357 135665 51329 20673 95904 15527 156410 147735 107963 185611 9516 181066 181938 6507 122388 3...
output:
180419 131590 199442 8 180067 158213 144567 16 91961 7982 22 24 19669 83774 100816 178989 144295 192496 98502 13918 82281 54825 153393 161001 96234 156005 189336 56 58 37839 183880 122217 109747 55664 126293 22945 74 189534 79704 80 82 84 86 100682 120483 92 94 96 98 75269 146292 104 78589 108 37105...
result:
ok ok (1 test case)
Test #28:
score: 0
Accepted
time: 1154ms
memory: 44384kb
input:
1 200000 262063 72841 66604 94581 51837 191542 123743 149876 10516 128822 123410 139111 103089 158541 56483 183570 157423 128256 118508 92821 129228 163748 28520 2448 160970 37107 90515 139799 163596 184374 16626 78012 98010 144666 155211 146459 60321 62391 172660 124463 39432 99102 80299 22916 1273...
output:
2 31035 6 164867 99811 160291 125133 16 18 138365 22 24 26 74182 70947 109108 62343 105338 38 162429 75597 61565 18405 48 196708 71848 130907 20868 58 60807 91016 93937 75266 80388 76705 149905 38478 187239 78 175823 94325 151920 35263 27483 14771 92 57370 192304 78921 143476 102 163414 104756 108 1...
result:
ok ok (1 test case)
Test #29:
score: 0
Accepted
time: 691ms
memory: 45576kb
input:
1 200000 301952 21951 38377 145264 141899 20286 189141 49248 10797 131312 186634 193391 7330 90758 178447 133654 28458 197098 132935 142271 123768 182413 51079 106749 37339 80111 160519 130329 80747 134297 17746 89135 104031 76611 66916 13891 148818 166668 148476 177606 78551 133202 121415 17109 114...
output:
47507 4 165905 108881 10 12 14 151844 64062 135459 178686 89048 58809 81329 32219 32 13005 121612 38 110421 157079 170249 86481 48 127910 10434 160129 115628 145488 83180 33521 70427 79111 67768 161846 150306 79151 39493 66203 147826 82 34551 66996 70816 164285 29599 52314 189157 98 26210 102 58100 ...
result:
ok ok (1 test case)
Test #30:
score: 0
Accepted
time: 632ms
memory: 47980kb
input:
1 200000 402105 169412 28307 39235 94949 120109 190352 59500 104359 75817 175560 50253 41771 83195 186648 20091 175725 106263 65825 156850 28786 72265 77440 104707 152961 108429 140785 176083 164531 173958 160585 89283 97448 72968 178690 182706 163213 64471 47768 59578 23108 25972 130392 101827 1729...
output:
10544 101873 24375 169389 183094 47537 132028 140541 53759 38585 137946 49595 170598 141369 199921 32 13119 105420 19478 84551 197262 44 123976 48 54531 9947 54 129503 58 58362 149581 88013 183175 16665 54997 182182 96359 140661 53568 129705 49544 84 151259 172039 62207 92 48925 176435 11517 42931 1...
result:
ok ok (1 test case)
Test #31:
score: 0
Accepted
time: 584ms
memory: 50504kb
input:
1 200000 499981 80537 142045 166196 27324 188484 59794 73011 62848 54982 32788 146891 120397 145977 112297 30732 34355 198025 193511 46734 37750 74321 75081 38173 123072 90782 51316 3345 153541 108762 97369 16828 137609 157439 191613 162866 51112 72589 170889 126524 133464 82570 115809 128563 112379...
output:
43784 48493 122718 81061 43790 63923 98010 109174 24149 51228 17919 131184 43484 156634 58530 96332 36945 15108 38 168783 63876 165691 118404 122947 15891 58362 6390 91666 108839 106571 90625 20803 66 65184 61102 38935 17006 11127 171802 148497 82 122481 169332 86867 68822 102449 14995 96 30670 5065...
result:
ok ok (1 test case)
Test #32:
score: 0
Accepted
time: 66ms
memory: 29580kb
input:
10000 9 14 7 9 6 7 6 3 3 2 3 5 3 4 3 8 7 8 2 7 4 7 3 1 7 1 7 5 9 3 5 4 2 3 4 5 4 1 2 1 65 120 48 33 48 27 65 28 21 48 48 4 3 28 39 48 48 10 48 50 32 13 19 48 52 24 48 24 48 15 48 31 65 48 52 19 60 48 49 41 22 28 48 20 18 48 2 28 25 48 1 48 2 48 28 23 52 20 28 51 28 11 52 63 59 28 28 36 48 44 31 28 2...
output:
2 7 6 8 2 4 25 61 12 29 57 26 40 37 60 20 43 24 56 28 6 32 7 23 16 15 41 18 31 65 5 52 3 4 58 22 38 53 2 7 6 8 23 12 19 31 25 21 33 24 20 3 30 32 34 2 4 6 2 4 6 8 1 12 2 4 6 8 10 3 1 16 18 2 8 6 1 21 17 14 16 12 19 3 9 2 4 6 7 10 9 3 4 11 8 10 3 2 4 6 8 10 12 14 2 7 6 2 4 6 7 10 12 2 4...
result:
ok ok (10000 test cases)
Test #33:
score: 0
Accepted
time: 85ms
memory: 30996kb
input:
1000 65 124 10 5 5 16 64 33 3 59 4 59 50 5 60 33 5 39 55 59 33 61 5 8 5 49 31 33 5 41 37 59 5 48 23 59 34 33 59 17 22 5 33 47 11 5 59 38 5 45 5 13 63 5 5 14 5 2 33 16 40 5 27 33 5 64 59 49 41 33 25 59 28 33 65 59 59 11 33 62 15 33 59 35 59 14 53 59 33 29 30 5 44 33 62 5 33 32 50 59 59 30 59 45 42 59...
output:
54 61 39 46 47 59 40 41 64 19 48 24 9 28 6 32 7 51 16 1 31 25 44 8 20 37 30 56 35 60 62 33 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 103 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 181 118 120 122 124 126 128 130 ...
result:
ok ok (1000 test cases)
Test #34:
score: 0
Accepted
time: 99ms
memory: 33776kb
input:
100 2720 5430 15 549 864 1152 549 492 1152 2121 366 1608 2226 1574 2096 1152 951 1152 279 1278 1574 232 2537 1152 806 1278 1988 1152 1574 2203 1239 1278 414 549 434 549 549 2020 1608 1319 2464 1574 1232 1152 1608 728 1453 1152 992 1608 1608 1637 1242 1152 1190 1574 1278 1587 2105 1278 2577 549 1178 ...
output:
2 4 637 8 594 12 14 16 18 20 2133 24 2057 28 30 1489 2545 36 38 1467 2115 785 975 1214 50 52 54 1221 1341 1523 62 456 66 68 70 72 74 968 78 2713 82 835 2329 409 90 92 94 2341 713 837 102 104 106 108 1893 112 114 116 1819 2059 1435 1175 126 128 1213 249 134 2559 285 1944 142 812 146 1768 636 1847 227...
result:
ok ok (100 test cases)
Test #35:
score: 0
Accepted
time: 124ms
memory: 36640kb
input:
10 11424 22838 10124 2930 2930 8210 6044 2930 9338 5243 2930 1990 8267 335 11369 2930 3640 2930 2930 8394 2930 4490 10225 5027 2930 7034 336 10225 6591 10225 2723 8267 3141 8267 9338 8308 8267 7647 2930 1471 9338 742 10225 2977 8267 4214 10232 6130 5050 6130 3536 9338 9338 810 8267 6841 8267 4313 59...
output:
2244 2651 82 6915 9318 12 7211 16 3590 5363 22 6347 11175 9530 7446 8897 1029 9930 3776 1815 5506 7996 5503 2871 9737 52 1313 56 58 9453 4783 6096 10234 10542 1138 3946 9047 10554 10453 6674 10323 6515 4889 88 1533 7436 10290 1683 8476 9520 11062 10694 8188 6152 1663 3866 8752 7604 9006 7135 916 419...
result:
ok ok (10 test cases)
Test #36:
score: 0
Accepted
time: 398ms
memory: 44660kb
input:
1 200000 399988 171813 28023 127391 157678 139161 157678 157678 158661 157678 6685 120596 157678 189440 28023 72845 28023 28023 155435 178088 157678 54821 157678 199920 7797 7797 23002 132615 7797 7797 114612 28023 98270 157678 29354 29544 28023 28023 6304 28023 86497 20726 7797 198021 7797 4578 157...
output:
115519 105111 86437 97080 99310 36326 106279 16 16425 177794 8439 114111 173862 146135 134943 11038 34 188487 98023 193121 177922 41263 174340 72382 29426 113623 53371 47465 143678 190973 102049 109316 134350 81832 66163 13985 163456 177518 19708 144040 82 65069 165604 76865 86710 77468 190568 14943...
result:
ok ok (1 test case)
Test #37:
score: 0
Accepted
time: 205ms
memory: 44368kb
input:
1 200000 399994 17358 78776 138799 189702 78776 115828 78776 76870 189702 82466 80014 189702 78776 129553 14969 78776 161279 120022 103978 161279 189702 90678 65648 78776 164898 189702 78776 4880 189702 17932 189702 29494 71164 78776 55663 78776 78776 25638 78776 51965 78776 73585 189702 190545 1173...
output:
163231 147761 188588 80159 125930 105664 159129 88811 65437 189866 79962 24 59815 3879 132816 56078 161383 36 96779 40 42 166252 46 185937 50 52 29215 188167 87658 60 62 18877 51477 68 70 96222 80905 98108 153031 80 82 80559 28665 53917 163573 100545 129749 133269 98 100 102 20511 164515 108 111795 ...
result:
ok ok (1 test case)
Test #38:
score: 0
Accepted
time: 140ms
memory: 44600kb
input:
1 200000 399996 43234 184957 104384 184957 184957 104551 48901 184957 130388 184957 184957 191112 93746 184957 51488 83793 46496 184957 184957 149525 48305 51488 16545 51488 155037 184957 51488 99541 5545 184957 184957 50631 147758 184957 141234 51488 33945 184957 119044 51488 99610 51488 162526 514...
output:
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 1...
result:
ok ok (1 test case)
Test #39:
score: 0
Accepted
time: 231ms
memory: 44412kb
input:
1 200000 399994 187117 14028 171699 93144 87566 171699 48194 171699 123842 171699 86963 78638 171699 77033 187117 79890 123219 171699 171699 63678 68921 187117 187117 91518 12750 187117 11203 171699 166545 171699 187117 75563 4708 187117 86963 26711 115930 86963 187117 102050 187117 66412 187117 962...
output:
122436 4 86673 48377 10 12 75883 102152 70769 8174 195213 24 26 142507 197713 32 34 21313 108504 39197 38287 39483 25215 48 10131 52 54 173151 35977 172401 62 64 66 68 70 72 74 76 152153 80 97360 74668 86 150003 178901 118998 94 96 98 100 102 198267 181297 123034 111729 182555 73147 37687 116085 127...
result:
ok ok (1 test case)
Test #40:
score: 0
Accepted
time: 115ms
memory: 44656kb
input:
1 200000 399996 158442 44824 102533 158442 144188 158442 180888 177991 158442 60658 130921 158442 11093 158442 158442 91269 177991 66366 45320 177991 852 158442 158345 177991 177991 101419 177991 60694 77523 177991 158442 64839 177991 97717 158442 15688 101326 177991 57416 158442 105648 158442 15844...
output:
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 1...
result:
ok ok (1 test case)
Test #41:
score: 0
Accepted
time: 583ms
memory: 44548kb
input:
1 200000 399984 132326 109212 15458 104058 141635 150556 42757 160742 104058 183026 140555 176509 105281 104058 98409 123058 115963 132326 110622 160742 124231 104058 9948 132326 149792 132326 186350 132326 114248 132326 117808 104058 149757 178717 20007 132326 103768 104058 160742 132129 181418 132...
output:
81033 157924 10931 184396 52782 50748 59000 160401 81680 94796 69723 146942 148444 116241 151494 22273 139174 162542 185631 144960 99052 30464 167466 118127 55040 171312 143335 160172 14100 64355 1552 166937 77178 81861 129111 18301 89934 82886 45857 95315 144471 84 29930 120450 113328 165947 11430 ...
result:
ok ok (1 test case)
Test #42:
score: 0
Accepted
time: 672ms
memory: 44932kb
input:
1 200000 399938 118765 169368 80877 55756 183643 55120 179690 39975 52846 39431 183643 142616 40237 9287 169765 51704 169765 196513 180903 78049 2468 127986 103196 92043 171000 183643 51970 16065 33387 150171 54791 100228 96040 51970 183643 73275 194778 116171 119619 51970 78820 25947 121977 74719 1...
output:
31626 98472 64598 150944 32079 183709 184994 4977 169022 148182 50216 110449 58279 140159 181802 5580 199502 174703 186158 70495 105369 135682 67071 155516 91082 12821 106149 196090 2191 98037 165322 116888 178076 173467 195269 28333 13393 82059 57101 138923 116348 112490 50117 93860 55299 24502 157...
result:
ok ok (1 test case)
Test #43:
score: 0
Accepted
time: 768ms
memory: 45160kb
input:
1 200000 399918 4808 186087 3193 20269 53579 193832 181866 119189 96009 51067 26071 110895 180290 198389 75156 67809 146896 88504 26232 199270 41761 194173 163583 73217 11161 69425 127108 172920 26071 136318 4808 20765 58003 13956 56475 127108 124690 96369 98349 88504 88504 129805 1116 75156 193832 ...
output:
159705 89849 41684 81076 183251 31811 88647 46350 134288 107289 52531 21784 951 147167 114144 97747 59663 36219 91499 179520 91006 106772 102429 32604 69355 85221 27202 174534 68451 178238 140878 141548 93159 116199 133102 123756 16769 191189 87540 176571 187790 22916 188469 126384 138408 65393 8887...
result:
ok ok (1 test case)
Test #44:
score: 0
Accepted
time: 668ms
memory: 46176kb
input:
1 200000 394970 67823 148797 176646 48645 130521 57454 24214 159679 58899 105974 31385 9900 98402 172520 136909 143412 104381 107770 158622 39611 181123 4031 93760 67853 87239 94179 102524 50092 53452 91220 161571 173978 140608 6827 8215 91048 101935 80437 20495 175157 85578 193822 117607 100231 195...
output:
163486 193090 42572 147662 146456 192406 8111 16 172895 185815 89891 110977 26 26101 142239 2856 97578 180772 107477 166885 78121 77515 46727 127740 184584 10551 142939 76393 15655 60 183943 170559 81111 51952 192006 6516 123905 32738 175482 100099 52167 33214 163517 75711 66645 128763 91756 56466 6...
result:
ok ok (1 test case)
Test #45:
score: 0
Accepted
time: 738ms
memory: 44688kb
input:
1 200000 324098 195943 81674 197522 192121 73692 10625 137597 30541 116880 163679 19609 78824 65138 65608 122246 18120 69217 48636 96269 102482 152468 42380 70492 187039 106990 158537 130005 170494 6227 16267 17532 42444 156564 89378 116737 22782 3890 98135 93103 18506 14764 134508 107699 107653 151...
output:
96756 10280 183215 78933 111595 128465 40933 40436 18 191661 26555 70923 111968 153187 154204 43672 147059 154016 106191 174559 33198 141465 33771 137211 62838 76289 105515 194395 144439 60 62 107130 66 194720 70 11365 93950 46497 117438 56042 54925 155561 188757 114759 186580 182591 94 19380 98 733...
result:
ok ok (1 test case)
Test #46:
score: 0
Accepted
time: 674ms
memory: 41940kb
input:
1 200000 200000 10712 34133 109916 81898 148586 4152 6534 159576 7955 53276 15698 110638 182088 163751 60650 31286 73846 141810 54346 154107 123853 122076 157857 161032 36509 82064 151785 146929 124102 184007 26103 42788 135406 130776 30940 184626 184648 4748 54625 68760 4035 142644 13678 114822 386...
output:
30420 64686 6 8 10 12 55260 16 102475 20 61270 48128 26 28 96387 91947 64688 181680 184707 40 150488 33745 46 175108 50 8935 95006 50896 43877 176349 87961 64 158887 68 70 7489 99527 95468 193657 80 78887 8706 52891 185809 72365 178978 105728 60671 158151 47732 87202 23364 1704 124382 134507 25490 1...
result:
ok ok (1 test case)