QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#432182#1282. Necklacechenxinyang2006AC ✓80ms21360kbC++205.2kb2024-06-06 21:28:042024-06-06 21:28:04

Judging History

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

  • [2024-06-06 21:28:04]
  • 评测
  • 测评结果:AC
  • 用时:80ms
  • 内存:21360kb
  • [2024-06-06 21:28:04]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n;
int col[200005],a[200005],buc[200005];

int K;
pii b[200005];
vector <int> S[200005];
bool cmp(int x,int y){
	return a[x] < a[y];
}

int lst,fst;
void pick(int c){
//	printf("pick %d\n",c);
	printf("%d ",S[c].back());
	S[c].pop_back();
	buc[c]--;
	lst = c;
	if(!fst) fst = c;
}

void constr(int idx,int sum){
	int j = 1;
	rep(i,1,sum){
		if(i % 2 == 0){
			while(!buc[j] || j == idx) j++; 
			pick(j);
		}else{
			pick(idx);
		}
	}
}

set <pii> SS;
void output(){
//	printf("output\n");
	int sum = 0,idx = 0;
	rep(i,1,n){
		sum += buc[i];
		if(buc[i] > buc[idx]) idx = i;
	}
	assert(2 * buc[idx] <= sum);
/*	printf("output:\n");
	rep(i,1,n) printf("%d ",buc[i]);
	printf("\n");*/
	printf("%d\n",sum);
	if(2 * buc[idx] == sum){
		constr(idx,sum);
		printf("\n");
		return;
	}

	SS.clear();
	fst = lst = 0;
	rep(i,1,n) if(buc[i]) SS.insert(mkp(buc[i],i));
	pii cur;
	while(1){
		auto it = prev(SS.end());
		cur = *it;
		if(2 * cur.first == sum) break;

		if(cur.second == lst){
			it = prev(it);
			cur = *it;
		}
		pick(cur.second);
		sum--;
		SS.erase(it);
		if(cur.first > 1) SS.insert(mkp(cur.first - 1,cur.second));
	}
	assert(cur.second != lst);
	int ed = -1;
	for(pii I:SS) if(I.second != cur.second && I.second != fst) ed = I.second;

//	printf("cur=%d final ed=%d\n",cur.second,ed);
	if(ed != -1){
		buc[ed]--;
		constr(cur.second,sum - 1);
		printf("%d ",S[ed].back());
		printf("\n");		
	}else{
		buc[cur.second]--;
		constr(fst,sum - 1);
		printf("%d ",S[cur.second].back());
		printf("\n");
	}

}

ll dp[200005][6];
vector <int> solve(int lim,int m){
//	printf("solve %d %d\n",lim,m);
	rep(i,0,n){
		rep(k,0,m) dp[i][k] = -linf;
	}
	dp[0][0] = 0;

	ll sum;
	rep(i,1,n){
		sum = 0;
		rep(j,0,min(lim,SZ(S[i]))){
			if(j) sum += a[S[i][j - 1]];
			rep(k,0,m - j) chkmax(dp[i][j + k],dp[i - 1][k] + sum);
		}
	}
/*	rep(i,0,n){
		rep(j,0,m) printf("%lld ",dp[i][j]);
		printf("\n");
	}*/
	vector <int> res;
	if(dp[n][m] <= -1e15){
		res.eb(-1);
		return res;
	} 
	int cur = m,_j;
	per(i,n,1){
		sum = 0;
		_j = -1;
		rep(j,0,min(lim,SZ(S[i]))){
			if(j) sum += a[S[i][j - 1]];
			if(cur >= j && dp[i][cur] == dp[i - 1][cur - j] + sum) _j = j;
		}
		assert(_j != -1);
		rep(j,0,_j - 1) res.eb(S[i][j]);
		cur -= _j;
	}
	rep(k,0,SZ(res) - 2){
		if(col[res[k]] == col[res[k + 1]]){
			if(k) swap(res[k],res[k - 1]);
			else swap(res[k + 1],res[k + 2]);
		}
	}
	if(col[res[0]] == col[res.back()]) swap(res[0],res[1]);

	rep(k,0,SZ(res) - 2) assert(col[res[k]] != col[res[k + 1]]);
	assert(col[res[0]] != col[res.back()]);
	return res;
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n) S[i].clear();
	fill(buc,buc + n + 1,0);
	rep(i,1,n) scanf("%d",&col[i]);
	rep(i,1,n) scanf("%d",&a[i]);
	rep(i,1,n) S[col[i]].eb(i);
	rep(i,1,n) sort(S[i].begin(),S[i].end(),cmp);

/*	printf("qwq\n");
	rep(i,1,n){
		for(int p:S[i]) printf("%d ",p);
		printf("\n");
	}*/	
	ll answer = 0;
	int sum = 0;
	rep(i,1,n){
		if(a[i] > 0){
			answer += a[i];
			buc[col[i]]++;
			sum++;
		}
	}

	int m = 0;
	rep(i,1,n) if(buc[i] > buc[m]) m = i;
	if(2 * buc[m] > sum){
		K = 0;
		rep(i,1,n){
			if(col[i] == m){
				if(a[i] > 0) b[++K] = mkp(a[i],m);
			}else if(a[i] <= 0){
				b[++K] = mkp(-a[i],col[i]);
			}
		}
		sort(b + 1,b + K + 1);
	//	rep(i,1,K) printf("(%d,%d) ",b[i].first,b[i].second);
		int ext = 2 * buc[m] - sum;
		rep(i,1,ext){
			if(b[i].second == m){
				buc[m]--;
				sum--;
			}else{
				buc[b[i].second]++;
				sum++;
			}
		}
	}

//	rep(i,1,n) printf("%d ",buc[i]);
//	printf("\n");
	if(sum >= 3){
		output();
		return;
	}

	rep(i,1,n) reverse(S[i].begin(),S[i].end());
	vector <int> res1 = solve(1,3),res2 = solve(2,4);
/*	for(int p:res1) printf("%d ",p);
	printf("\n");
	for(int p:res2) printf("%d ",p);
	printf("\n");*/
	if(SZ(res1) == 1 && SZ(res2) == 1){
		printf("-1\n");
		return;
	}
	if(SZ(res1) == 1){
		swap(res1,res2);
	}else if(SZ(res2) > 1){
		ll awa = 0;
		for(int p:res1) awa += a[p];
		for(int p:res2) awa -= a[p];
		if(awa < 0) swap(res1,res2);
	}
	
	printf("%d\n",SZ(res1));
	for(int p:res1) printf("%d ",p);
	printf("\n");
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

-1
4
2 4 1 3 
4
7 2 4 5 
4
3 2 4 1 

result:

ok 4 cases.

Test #2:

score: 0
Accepted
time: 47ms
memory: 9896kb

input:

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

output:

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

result:

ok 36398 cases.

Test #3:

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

input:

36169
6
6 3 6 4 2 1
1 7 1 4 3 5
1
1
4
8
5 1 6 7 7 3 6 2
10 6 4 9 4 6 9 6
2
2 2
10 9
2
1 1
4 2
5
5 1 2 1 4
1 1 10 7 1
9
7 5 9 1 8 3 2 7 2
9 8 7 1 6 9 6 5 2
2
2 1
5 9
9
4 8 1 6 9 4 1 9 7
9 3 5 4 3 1 5 9 7
8
1 7 2 7 3 3 5 3
6 4 3 10 6 4 7 2
6
4 5 2 5 1 4
7 6 2 3 7 3
4
4 1 2 3
9 3 7 9
10
3 5 8 9 3 2 7 1...

output:

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

result:

ok 36169 cases.

Test #4:

score: 0
Accepted
time: 50ms
memory: 7808kb

input:

36365
8
3 5 2 3 3 5 8 4
-5 -6 -1 -9 -8 -5 -7 -8
3
1 2 2
-7 -5 -4
5
2 3 1 2 4
-6 -10 -5 -3 -10
2
2 2
-9 -8
7
7 3 3 2 6 5 6
-7 -7 -10 -7 -7 -10 -4
7
6 2 4 6 5 2 5
-9 -8 -10 -1 -6 -3 -6
8
7 4 8 4 6 7 1 6
-4 -4 -6 -4 -4 -10 -6 -2
10
3 6 1 1 4 1 2 8 6 1
-5 -9 -9 -5 -10 -1 -5 -5 -1 -4
4
2 2 3 3
-7 -4 -1 -...

output:

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

result:

ok 36365 cases.

Test #5:

score: 0
Accepted
time: 40ms
memory: 9860kb

input:

6663
19
16 11 18 18 10 17 15 8 9 14 19 2 14 18 17 19 3 17 14
10 9 5 -2 3 -7 2 6 -2 5 -4 3 -6 9 6 7 4 0 -7
41
21 18 26 20 37 38 31 37 12 8 17 2 27 4 39 26 9 32 40 12 2 35 1 31 36 28 41 9 25 1 11 21 30 37 31 36 6 4 21 34 33
-3 0 -9 4 9 5 0 -2 -10 -3 -3 8 -6 7 -7 9 0 3 -2 10 -9 1 2 3 5 -2 6 7 6 -6 -2 5...

output:

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

result:

ok 6663 cases.

Test #6:

score: 0
Accepted
time: 57ms
memory: 8132kb

input:

1343
130
55 112 18 93 56 43 35 39 76 130 10 57 65 9 9 40 19 24 73 119 68 122 74 61 125 48 69 112 79 93 33 113 50 34 58 123 15 85 58 102 130 129 69 9 10 23 103 8 50 105 105 95 47 35 31 78 130 100 34 79 114 50 109 23 49 35 28 32 107 75 45 18 10 62 110 111 56 28 48 70 91 1 50 100 53 58 70 22 7 46 95 12...

output:

60
116 10 9 87 27 21 39 97 26 94 7 120 108 41 42 125 22 105 20 61 98 76 103 51 40 117 91 81 109 29 115 70 23 123 80 43 95 86 12 85 33 79 90 71 16 66 31 68 55 78 18 64 17 100 92 11 15 48 118 104 
85
97 16 47 101 95 90 87 78 165 37 39 30 128 72 146 63 75 99 140 15 65 178 33 27 69 6 145 167 152 154 41 ...

result:

ok 1343 cases.

Test #7:

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

input:

137
1888
459 530 933 1784 1671 1327 610 1409 580 1014 1261 1770 34 1663 97 53 244 1144 298 26 706 34 1226 1667 1832 1488 247 1710 1109 267 1435 1262 1869 1872 1267 10 264 911 433 797 1841 590 250 468 1415 1573 457 1747 1343 480 1162 784 1664 1664 1888 374 453 282 1567 516 1855 1814 562 1004 785 1073...

output:

939
494 448 179 578 88 769 643 1348 915 999 861 217 51 445 911 751 1155 613 60 1576 939 149 103 1351 812 1282 275 1737 41 250 311 1662 1454 1786 1452 1157 449 876 1474 759 312 316 687 28 753 496 760 92 1853 1829 614 1285 294 228 827 1078 374 435 1160 1328 289 658 958 957 923 1700 558 904 1292 466 80...

result:

ok 137 cases.

Test #8:

score: 0
Accepted
time: 57ms
memory: 8000kb

input:

133
1989
1728 1930 1845 787 894 1256 1355 1168 1599 1057 1253 1519 1665 638 540 1269 1704 206 571 458 952 1901 1874 937 147 1016 446 1179 503 904 1800 1607 558 1430 1286 1084 735 690 1770 251 910 187 1427 833 244 280 328 1528 1194 1484 598 421 815 49 1907 1651 1821 924 809 1632 1167 1129 440 476 192...

output:

1989
307 1085 1517 72 1858 811 459 1968 691 1365 1427 1255 412 1493 1610 745 1176 781 1214 700 383 1843 1495 208 1656 1461 764 1243 1183 229 752 63 369 397 293 932 1402 930 1201 1752 1062 74 675 1231 1665 1178 1974 312 57 1209 31 481 1925 1870 612 1299 639 1007 1649 1370 1766 1661 480 786 1088 991 1...

result:

ok 133 cases.

Test #9:

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

input:

134
1470
823 453 281 76 908 347 944 990 913 585 648 660 991 219 646 422 846 1320 606 541 1324 1454 1152 1032 32 1364 459 879 60 652 1249 476 698 880 762 1098 1413 474 707 1200 935 594 1203 172 179 746 1224 83 259 1 337 431 505 407 1308 763 762 709 169 340 363 1075 845 890 82 322 1270 1044 781 851 90...

output:

3
1097 107 672 
3
1040 612 1084 
3
1158 584 1839 
3
340 715 241 
3
266 1382 206 
3
575 822 769 
3
289 1226 994 
3
65 817 1291 
3
1440 984 412 
3
425 777 1431 
3
1063 1069 780 
3
1317 1199 1164 
3
1057 1338 813 
3
987 818 717 
3
1266 1053 881 
3
579 441 487 
3
459 1062 774 
3
324 675 371 
3
939 360 6...

result:

ok 134 cases.

Test #10:

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

input:

133
1190
251 1086 819 1186 473 671 186 1112 685 40 436 817 1185 359 278 961 818 304 706 428 448 1013 82 1102 433 706 824 895 601 869 850 859 283 840 929 200 706 821 968 418 1003 902 1108 964 130 257 984 576 923 190 916 5 955 192 128 796 899 358 860 925 1143 122 873 83 824 1183 877 401 285 546 364 40...

output:

3
750 180 261 
3
790 962 166 
3
868 954 1583 
3
1313 134 153 
3
1293 1351 743 
3
209 236 553 
3
1549 1224 1587 
3
528 831 105 
3
657 1200 256 
3
1837 160 198 
3
138 861 553 
3
949 930 577 
3
722 915 272 
3
1178 425 368 
3
235 100 951 
3
389 133 1062 
3
487 585 1025 
3
630 74 256 
3
236 433 107 
3
19...

result:

ok 133 cases.

Test #11:

score: 0
Accepted
time: 44ms
memory: 9924kb

input:

134
1672
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

828
574 1120 342 1245 332 1381 920 1567 722 1213 413 1585 664 1413 180 1534 394 1127 523 1039 419 1379 262 1626 505 1371 4 1515 817 1299 64 1370 563 1244 569 1295 603 1173 35 1409 450 1337 714 1136 119 1440 677 1238 361 1327 140 1474 455 1313 530 1093 751 1664 776 1226 566 1443 279 1589 48 992 599 1...

result:

ok 134 cases.

Test #12:

score: 0
Accepted
time: 53ms
memory: 8880kb

input:

12
18055
16797 6461 5661 258 15361 9217 9880 14473 16352 214 57 8242 16295 4901 8533 17041 13453 14844 17977 8109 17068 8678 7580 1720 1113 1718 10508 15915 2063 9193 3138 724 17043 15873 3164 4858 4654 7380 8811 8952 15967 9649 3576 9425 5004 9380 11990 8967 17597 16447 4348 13906 3299 7178 12969 1...

output:

8961
8181 10146 1425 1323 1624 9076 14431 4825 9933 2237 4197 15506 4069 1455 2008 18053 10685 9231 9798 5671 14844 16478 7793 15526 8476 4749 5863 17723 2643 11182 717 1855 4017 16742 9710 14904 11215 8864 8489 16573 3901 10229 8985 5222 9646 7178 1630 11770 15290 9 11747 10516 16185 5774 3353 5648...

result:

ok 12 cases.

Test #13:

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

input:

14
17434
9548 3285 2124 13465 5769 15776 17003 212 10049 15889 16817 4989 14153 13830 13062 3670 4025 3284 15928 617 3990 1450 16869 731 1918 10375 9806 12155 11182 847 8356 3496 3746 8923 11735 12340 10439 9343 2388 10754 3015 10844 4555 4572 15134 9060 9591 4313 4873 10529 16805 9835 11013 5647 15...

output:

17434
5865 4495 3568 1422 14191 1872 11 15826 12340 2621 14474 207 2243 15199 9372 2042 9490 5821 3279 16794 10510 8184 14495 10824 3077 8514 3662 12531 4115 16412 93 946 2643 10573 17096 16291 6115 309 3687 4662 7398 1223 12439 11519 5637 13713 8117 8112 6340 1627 2032 580 3947 2859 6826 10058 1212...

result:

ok 14 cases.

Test #14:

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

input:

12
14655
11411 161 1024 7539 13177 6370 4724 10192 11161 7719 10455 11482 5760 3288 14566 7833 8877 10020 10600 808 3418 4532 587 10094 615 7241 1377 10067 960 10186 4614 1777 7424 8565 1745 6102 10828 11771 4154 13404 7074 8342 3613 363 13116 1831 1796 13398 3046 1879 10337 6921 2467 4112 5735 1220...

output:

3
8137 14267 3500 
3
9553 4545 8885 
3
13413 4224 9864 
3
16709 7718 11083 
3
3038 4727 9516 
3
2383 13341 5913 
3
11588 9967 4235 
3
14772 5299 11848 
3
1111 154 2371 
3
9866 9342 8020 
3
7182 14971 9124 
3
7086 13056 15722 

result:

ok 12 cases.

Test #15:

score: 0
Accepted
time: 44ms
memory: 9448kb

input:

14
14034
10803 1737 4691 2728 3742 3502 3140 4884 11294 1581 10643 13426 7023 13376 7237 12200 1462 12551 12040 524 11824 7685 4122 4225 9127 9188 709 6498 9670 554 13326 10381 7789 4277 12503 6045 4994 6543 8010 13513 1135 5044 13759 388 6604 1461 11927 7152 10411 2045 5304 13655 5103 12866 3144 12...

output:

3
5776 8444 13704 
3
10573 14255 1002 
3
3139 10122 8770 
3
9494 5579 1420 
3
14409 1901 6078 
3
6393 12504 8034 
3
5701 808 2254 
3
2517 4605 1063 
3
8579 4334 2725 
3
11907 10153 16013 
3
7044 12895 1002 
3
8058 13696 4820 
3
14861 17497 13562 
3
1145 9192 2857 

result:

ok 14 cases.

Test #16:

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

input:

12
11255
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

5686
5846 9291 5418 9105 4130 10917 1685 6921 6110 6786 6078 9451 2903 10309 3604 8379 4602 6567 3860 10465 4322 9016 5850 9135 4967 10902 1283 10577 2013 7753 861 6565 183 10366 5428 10378 2241 9935 6314 9247 1372 8785 1114 9383 5520 7675 825 8384 524 9108 5916 6988 2692 8145 814 10823 4633 9329 55...

result:

ok 12 cases.

Test #17:

score: 0
Accepted
time: 64ms
memory: 12592kb

input:

3
58721
24434 9260 24075 48000 15976 20173 35443 51833 19066 41037 54110 1481 19903 51532 3423 31435 3508 11994 15714 163 55971 31702 36494 4158 51738 44184 24638 56542 45429 9219 45527 15074 28047 37930 45584 56610 49878 37478 38487 34277 34534 20191 11345 52669 4052 58673 1053 27733 28790 52960 35...

output:

29420
53009 38400 52759 57474 9486 12053 56021 27963 55364 52533 10984 20798 56893 42384 7433 10461 2644 15255 34045 49106 8701 57439 7001 18162 11049 13395 16804 58709 30828 24242 50559 27320 30068 37681 2340 51413 4544 41543 49679 57381 15645 43175 52893 7572 4726 13946 9886 35534 40408 33743 2645...

result:

ok 3 cases.

Test #18:

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

input:

2
77676
27968 75961 21244 54489 71767 46141 53503 13873 18582 11076 64477 51679 6938 36146 38280 58457 28777 38269 14895 25463 52274 57117 4973 40172 6470 60885 61948 14050 909 60043 4187 52377 43750 1600 31546 6977 53526 11677 24682 72371 5910 18647 65163 16777 73668 26432 10296 39627 23007 71448 1...

output:

38748
13314 51278 29926 15938 50245 13517 32698 48265 31055 2603 6152 1048 69301 36060 71891 70690 75987 25821 71379 25441 15714 9400 37543 6469 51572 63833 67860 22020 42000 34928 48323 59113 50480 40881 68312 33326 30925 21441 54218 12968 76253 16910 10448 9330 69379 35316 60579 21060 26642 66024 ...

result:

ok 2 cases.

Test #19:

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

input:

1
200000
84638 180660 96676 145207 33392 79870 171900 125536 96004 63088 55821 129766 161448 131134 107191 45727 177392 29632 142432 198535 92403 141810 68401 132218 189131 53237 157976 172219 186777 173068 5956 125297 154368 15264 18156 9572 126885 111293 89928 31940 95413 63059 80790 20899 106847 ...

output:

99872
2791 183251 196914 128612 197189 138474 47952 25296 90692 139068 110598 135367 66614 110928 88250 129649 18066 180363 86011 151521 101347 46837 52557 151649 16685 24834 114034 88607 135209 48626 141922 155753 151096 89704 182627 23895 85071 37692 4629 96567 39028 52430 51323 153528 151797 1863...

result:

ok 1 cases.

Test #20:

score: 0
Accepted
time: 67ms
memory: 18544kb

input:

1
200000
778 193918 126153 94460 79465 19149 155888 59691 186 123527 158668 162560 163689 134161 155108 117642 81846 27650 15185 86475 183284 82023 110081 78779 107852 147458 182837 86532 62456 92294 124739 67588 130504 17373 180052 77006 156960 98530 80039 48041 89336 28839 47948 187599 100635 2993...

output:

99338
159461 126074 41731 54868 124214 44271 102925 125112 20879 118178 129486 67325 108280 102929 157804 76466 146615 122454 124674 24840 120383 131522 32177 109068 192331 42609 34542 24937 3840 192487 56276 131388 133421 121825 58753 189522 196069 153071 142537 171140 180665 28681 107254 6634 9215...

result:

ok 1 cases.

Test #21:

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

input:

1
200000
149623 174471 188335 19522 182434 191133 139876 193846 104368 151263 151116 138458 157418 95972 3025 198068 129404 25668 79426 182928 131062 132637 184464 192636 18060 8975 7698 176652 162326 11520 35009 177175 73936 19482 183164 111736 154331 85768 13254 121038 74746 3132 182403 145788 859...

output:

100222
55350 6739 90983 32253 149552 158255 39035 112208 124887 301 2424 100225 119178 154251 89164 12718 36334 92106 45713 41252 139435 171717 172947 102531 142952 109038 65564 21473 156110 42129 139423 112320 119865 160814 122275 117219 97668 137399 7897 76534 109837 89593 129570 196980 80596 3842...

result:

ok 1 cases.

Test #22:

score: 0
Accepted
time: 80ms
memory: 19864kb

input:

1
200000
98467 179217 17812 1480 61210 20012 123864 160706 8550 20215 78155 138548 159660 98999 50942 69983 33858 56390 9075 46676 78840 40146 50335 139197 128268 103196 89455 58260 62196 154939 88383 62570 50073 54294 145060 170657 184406 48814 170660 104434 68669 168913 141049 136681 79698 96616 1...

output:

100247
100037 136879 42467 70922 123746 160553 68746 132143 4112 176997 62157 111005 51650 86020 164323 198225 15402 186799 107680 194309 73279 100393 46497 150347 35324 57294 138158 59724 20697 168191 91348 152388 162391 39369 197203 25059 166070 57617 104352 23797 168026 154256 4246 189153 56673 3...

result:

ok 1 cases.

Test #23:

score: 0
Accepted
time: 65ms
memory: 12968kb

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

118792
111712 151193 29619 145391 33018 155592 36783 143043 74448 140127 23580 145892 101600 149755 18478 125471 108249 135290 49620 138056 106750 196327 15475 139932 115393 141517 68903 189581 32022 141168 1206 144537 117239 163826 33856 148739 84519 181996 79128 149834 52780 154314 118433 186845 3...

result:

ok 1 cases.

Test #24:

score: 0
Accepted
time: 66ms
memory: 13272kb

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

123120
27637 155220 14954 159496 25225 148561 40993 157686 2688 187435 57831 158974 51897 183018 67367 141884 1350 122098 41698 121031 116642 133243 106095 143373 98154 143091 30589 127935 49629 186021 55675 129647 83098 150290 107454 193239 94517 127496 8042 182724 75387 118112 47769 154339 38819 1...

result:

ok 1 cases.

Test #25:

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

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

129882
1160 136435 477 127829 41881 124720 48095 150200 30738 110192 85922 132357 33223 114792 69622 132689 33823 130726 42648 105259 69051 110268 42929 158540 93800 146712 27926 156810 73884 124150 100791 164316 16538 163902 47971 122039 16054 118154 16502 123301 71904 128427 97985 122719 65671 136...

result:

ok 1 cases.

Test #26:

score: 0
Accepted
time: 60ms
memory: 12560kb

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

129428
31376 140521 38214 123608 53187 107667 87023 190980 51263 125462 13924 134915 53378 141904 40185 120292 17332 182266 16338 145249 84137 195811 71016 129374 45837 173762 76991 169205 81842 146350 79145 144723 53751 130122 79819 197460 30483 103938 11739 116088 65279 169749 15930 132530 68240 1...

result:

ok 1 cases.