QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383484#8561. Restoring a Permutationbulijiojiodibuliduo#AC ✓64ms21012kbC++171.4kb2024-04-09 14:47:452024-04-09 14:47:46

Judging History

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

  • [2024-04-09 14:47:46]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:21012kb
  • [2024-04-09 14:47:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=201000;
int n,a[N],deg[N],b[N],ret[N],v[N];
VI e[N];
queue<int> q;

void add(int x,int y) {
	e[x].pb(y);
	//printf("cnm %d < %d\n",x,y);
	deg[y]++;
}
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) {
		scanf("%d",&a[i]);
		if (v[a[i]]!=0) add(i,v[a[i]]); // i <
		if (a[i]>1) add(v[a[i]-1],i);
		v[a[i]]=i;
	}
	rep(i,1,n+1) scanf("%d",&b[i]),v[i]=0;
	per(i,1,n+1) {
		if (v[b[i]]!=0) add(i,v[b[i]]); // i <
		if (b[i]>1) add(v[b[i]-1],i);		
		v[b[i]]=i;
	}
	rep(i,1,n+1) if (deg[i]==0) {
		q.push(i);
	}
	int tot=0;
	while (!q.empty()) {
		int u=q.front(); ret[u]=++tot;
		q.pop();
		for (auto v:e[u]) {
			--deg[v];
			if (deg[v]==0) q.push(v);
		}
	}
	rep(i,1,n+1) printf("%d ",ret[i]); puts("");
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11988kb

input:

5
1 1 1 2 3
3 2 1 1 1

output:

5 3 1 2 4 

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 12224kb

input:

6
1 1 2 2 3 3
2 1 2 1 2 1

output:

3 1 5 2 6 4 

result:

ok 

Test #3:

score: 0
Accepted
time: 2ms
memory: 11172kb

input:

1
1
1

output:

1 

result:

ok 

Test #4:

score: 0
Accepted
time: 2ms
memory: 11828kb

input:

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

output:

4 6 7 1 9 5 8 3 2 10 

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 11840kb

input:

20
1 2 3 3 3 2 4 3 4 5 3 5 6 2 5 4 7 5 5 6
1 3 6 5 4 2 4 3 3 5 2 4 4 1 3 1 3 2 1 1

output:

1 5 16 14 10 3 13 7 9 19 4 17 18 2 15 6 20 12 8 11 

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 12212kb

input:

30
1 1 1 2 1 1 1 1 3 1 2 3 3 4 2 4 2 3 4 4 2 2 5 5 6 7 7 3 8 5
11 10 9 9 8 7 6 2 8 1 5 7 5 6 4 5 3 3 4 3 2 1 3 2 2 3 2 1 2 1

output:

30 28 24 27 21 17 14 3 29 1 10 23 13 20 8 16 6 7 12 9 5 2 19 15 18 26 22 4 25 11 

result:

ok 

Test #7:

score: 0
Accepted
time: 2ms
memory: 11440kb

input:

40
1 1 1 2 2 2 3 4 4 4 5 5 6 6 6 7 8 2 8 3 7 9 7 8 9 4 6 9 10 10 4 5 10 11 12 8 7 10 10 12
9 5 1 9 4 2 2 7 6 3 8 3 7 5 3 5 6 1 5 1 4 5 3 3 4 2 2 3 5 4 1 1 3 3 3 2 1 2 1 1

output:

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

result:

ok 

Test #8:

score: 0
Accepted
time: 2ms
memory: 12124kb

input:

50
1 2 1 3 2 4 3 4 5 5 3 5 4 4 6 2 7 5 4 1 6 4 5 7 3 6 1 4 5 6 5 5 6 5 5 3 1 3 2 7 6 2 8 4 7 6 8 8 6 9
8 10 4 13 6 15 7 12 14 13 6 12 11 10 12 4 12 11 9 3 11 7 10 11 5 10 2 5 9 9 8 7 7 6 5 4 1 3 2 4 3 1 4 1 3 2 3 2 1 1

output:

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

result:

ok 

Test #9:

score: 0
Accepted
time: 7ms
memory: 12964kb

input:

20000
1 2 1 1 2 2 3 4 4 3 5 4 5 2 2 6 7 4 8 1 1 7 5 2 3 8 6 4 3 7 9 4 8 5 5 7 9 3 8 4 6 4 5 5 9 10 6 7 10 6 9 7 5 8 11 11 9 7 4 10 10 5 5 11 6 12 4 13 2 4 9 9 7 14 3 4 5 9 10 9 11 8 14 12 13 10 14 12 11 5 6 12 15 7 13 13 16 5 17 10 7 14 12 1 8 9 15 16 13 13 14 9 6 16 9 10 16 13 17 12 18 10 14 15 11 ...

output:

15900 18140 10021 2584 12178 8695 9334 18233 17774 9173 19117 13083 13353 7634 4777 16616 18184 9752 19518 2260 440 17726 9781 2073 2602 18284 9910 8789 2294 11712 19152 7261 13319 8823 8758 9986 18095 2162 10020 3916 9717 3013 8214 6379 15590 17773 7724 9947 17678 7700 13419 8727 6349 9620 19538 19...

result:

ok 

Test #10:

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

input:

40000
1 1 2 3 4 5 6 5 4 2 3 6 2 4 6 7 4 5 8 1 6 6 7 2 3 8 9 9 9 5 5 4 6 10 5 11 6 7 10 8 10 1 4 11 11 8 10 2 12 9 11 8 12 10 12 6 9 9 13 14 11 2 13 8 10 11 6 3 11 5 12 12 14 13 15 14 9 6 14 16 7 8 8 10 9 2 3 11 13 15 8 15 10 12 8 15 5 11 11 9 14 9 12 13 12 16 11 16 14 14 17 15 12 18 11 10 13 12 16 1...

output:

34643 2152 14736 18002 27147 35170 39507 28766 25048 5363 5615 36453 4383 13430 34105 35628 7724 13964 39689 962 33112 15333 23745 2526 2738 23827 33376 32781 25524 12942 9684 4511 15301 36858 5581 39527 9325 13469 36812 23060 27566 572 2810 35106 34817 17231 26878 1640 39801 24372 33838 16882 35558...

result:

ok 

Test #11:

score: 0
Accepted
time: 20ms
memory: 13648kb

input:

60000
1 2 1 1 3 2 2 2 3 1 3 4 4 2 5 6 5 4 5 5 5 2 4 6 3 5 7 7 4 3 3 4 6 8 3 7 9 2 10 3 10 10 2 8 8 11 5 4 5 12 4 5 2 8 9 6 9 10 11 10 8 12 9 11 12 9 10 6 11 12 6 11 12 2 9 6 13 13 11 7 12 7 10 8 9 13 13 7 10 12 7 14 11 3 12 8 13 15 8 14 9 9 6 7 12 9 14 10 3 11 13 11 10 15 8 11 11 16 12 12 3 13 9 13 ...

output:

40789 50642 9946 1348 54225 47859 30417 26132 52421 9 26883 55159 48736 25189 54153 54832 54075 37873 52092 42195 40411 12249 28971 42250 26399 29448 48664 47930 26616 23881 16254 18845 29823 48381 13521 30478 52356 6897 55497 8138 54777 54224 1796 37934 36432 55554 23648 11789 22444 55836 10132 142...

result:

ok 

Test #12:

score: 0
Accepted
time: 25ms
memory: 14596kb

input:

80000
1 1 2 3 2 4 5 2 3 1 4 4 5 3 5 4 6 6 7 7 5 7 4 8 2 5 9 7 8 10 6 8 7 11 12 7 3 11 7 3 9 10 8 4 4 9 5 11 8 12 6 7 3 13 8 10 11 12 4 8 9 14 4 5 8 10 13 4 14 6 15 10 12 11 15 13 12 9 7 13 11 14 12 7 5 13 10 12 16 13 16 14 17 18 15 14 15 16 14 15 7 13 16 18 11 6 17 9 12 8 11 18 17 6 15 13 10 9 18 13...

output:

53197 105 40897 58219 13594 58444 67751 4661 27057 26 55328 28168 37531 10623 35931 22119 40386 36062 76813 66322 35353 55452 19877 58148 1386 27004 66956 46640 55048 67684 27532 50024 40524 72883 79179 35297 10584 67750 31973 6936 55390 56339 45950 10545 8555 52410 9715 67615 41036 78378 18564 2300...

result:

ok 

Test #13:

score: 0
Accepted
time: 32ms
memory: 15760kb

input:

100000
1 1 2 3 1 1 2 4 3 3 4 2 4 5 4 6 6 7 6 5 3 8 3 5 4 4 5 8 4 7 8 8 6 5 5 6 6 4 5 9 1 7 6 5 8 4 9 10 11 8 9 10 10 10 9 6 11 7 1 2 8 12 10 13 7 11 8 5 10 8 10 8 14 9 4 11 10 12 13 6 8 10 8 8 2 4 11 10 14 6 3 7 15 5 2 12 5 13 5 8 14 4 6 11 9 7 9 14 13 5 14 10 4 11 8 12 4 15 3 11 16 5 14 13 10 16 14...

output:

66781 51699 62494 95413 49272 9125 31919 95796 93316 42272 93817 9994 44721 61838 44236 79373 67127 81875 66364 60628 30577 95333 12191 55665 42663 32701 44649 95243 30133 67613 81955 78342 60539 40936 40868 51269 42729 22063 30322 79141 1854 50004 42600 27636 67210 19346 78268 92811 94722 62417 726...

result:

ok 

Test #14:

score: 0
Accepted
time: 34ms
memory: 16992kb

input:

120000
1 2 3 2 2 3 3 3 2 4 4 2 5 3 3 4 5 4 6 7 5 5 8 9 5 8 9 10 9 10 10 6 10 11 4 11 12 7 6 11 8 5 10 6 13 12 12 11 13 6 12 13 9 12 14 6 7 13 4 5 5 6 7 8 7 13 3 15 2 14 10 15 15 9 10 15 16 17 8 15 14 16 17 10 13 18 8 16 11 9 14 14 10 17 18 11 1 17 18 15 19 19 16 17 9 20 11 12 15 16 20 20 10 13 14 21...

output:

2678 99725 110790 86087 16168 107874 97372 60064 8058 112771 74834 3543 104118 49555 7310 28125 38874 24175 43992 47343 36379 28227 67069 99805 24360 50257 65029 112681 58586 93366 74524 43431 62702 99643 17916 75961 109627 43917 38251 68362 44064 22556 59728 27518 112590 103427 96051 65107 97701 24...

result:

ok 

Test #15:

score: 0
Accepted
time: 43ms
memory: 18232kb

input:

140000
1 1 1 1 2 3 3 2 3 4 2 5 1 3 5 6 5 6 3 2 5 6 7 4 5 5 4 7 5 5 1 6 6 6 7 6 6 7 6 8 9 9 10 7 10 11 11 8 9 9 3 1 10 11 12 11 11 13 10 12 12 13 12 2 14 13 13 15 12 2 16 16 9 15 10 3 14 9 6 14 7 14 10 14 6 8 15 15 16 11 15 16 17 5 18 4 19 5 17 18 15 13 11 20 14 10 6 10 20 12 15 13 19 11 20 15 7 19 1...

output:

134861 112749 70275 13095 43343 134453 132178 22809 48356 78973 14657 139934 2803 36538 120601 131219 104217 116126 15256 14340 89265 104491 134148 38498 87025 40995 18415 122841 30787 19008 1921 69515 47940 47601 103570 38423 34423 67761 33410 68852 113536 91476 115995 33602 108229 125448 124434 34...

result:

ok 

Test #16:

score: 0
Accepted
time: 48ms
memory: 18700kb

input:

160000
1 1 2 1 2 2 3 4 3 5 4 2 5 6 6 6 3 5 4 6 5 6 4 7 5 8 2 8 5 6 7 9 7 10 11 2 1 12 2 4 13 9 8 8 5 9 14 3 12 10 6 3 9 12 10 11 4 11 12 13 14 15 8 3 2 13 11 3 12 12 9 3 13 4 14 11 16 6 15 13 10 7 8 11 16 14 10 13 14 5 15 14 11 16 12 12 17 8 13 18 13 15 13 5 12 17 17 8 16 7 10 18 17 5 12 13 17 6 7 9...

output:

76313 51070 140831 1801 89539 29192 36470 78826 36096 112836 57564 13606 65110 96439 94469 85487 24180 61617 37177 70629 55405 57952 27524 78314 32800 128450 10000 93956 27785 32504 78245 109878 32752 126894 133145 5991 352 152700 1680 24332 152824 96816 81688 64441 24381 73195 156977 23715 138119 9...

result:

ok 

Test #17:

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

input:

180000
1 2 1 1 2 2 2 3 3 3 4 5 2 6 1 4 3 5 2 6 4 1 5 7 8 8 7 6 9 6 2 3 4 7 10 8 7 5 10 6 7 5 6 9 7 3 11 11 5 12 9 13 4 11 8 9 10 7 12 8 8 9 10 11 11 12 13 12 13 7 8 9 14 14 14 14 12 9 3 6 10 15 3 7 15 1 16 11 3 11 16 2 17 4 11 10 13 17 17 18 5 13 7 14 18 5 6 10 12 13 13 12 8 16 18 17 19 15 11 4 13 6...

output:

68352 97217 29256 18858 93144 85289 45666 140078 93608 56468 128258 133432 36636 133747 17650 61905 40652 78085 26821 114668 54307 4671 68266 124053 163981 134461 117606 110110 140295 73610 13392 24686 25690 89578 155175 109680 78248 40362 141064 49499 72714 27948 48222 129429 62096 23747 155058 152...

result:

ok 

Test #18:

score: 0
Accepted
time: 59ms
memory: 20720kb

input:

200000
1 2 3 1 2 3 3 4 3 5 6 7 2 8 6 7 3 9 4 7 10 5 6 4 3 8 10 11 7 4 8 9 3 12 8 1 6 10 10 7 13 9 11 5 6 7 4 10 11 11 4 7 3 12 13 5 5 14 13 2 8 9 8 9 4 14 5 9 10 10 11 15 10 6 12 4 7 1 12 11 13 6 15 6 6 15 3 13 16 15 2 8 16 11 14 17 9 8 10 12 4 15 9 7 13 14 13 5 14 9 8 16 13 17 3 14 18 11 7 11 19 15...

output:

84661 187199 197375 2843 28743 174204 78930 93967 71302 104756 129897 171327 11732 174051 104853 138710 54177 179202 63820 113879 197589 68815 85091 54798 31643 155794 187348 195869 106911 54475 138354 158298 31296 197780 112069 2713 81593 183832 180209 83349 197864 114470 190140 55710 64353 70568 3...

result:

ok 

Test #19:

score: 0
Accepted
time: 63ms
memory: 20788kb

input:

200000
1 1 1 2 3 4 1 2 3 4 5 4 2 3 1 3 5 4 6 7 5 6 5 6 5 6 2 4 5 3 6 7 4 1 8 4 8 8 8 5 9 9 4 5 3 5 5 4 6 10 7 10 9 2 10 6 7 11 2 4 11 12 7 3 13 12 10 5 5 2 13 14 8 3 14 6 6 8 9 9 3 14 10 13 14 10 7 15 8 14 8 13 6 15 10 4 16 7 14 1 10 4 7 15 1 11 11 13 13 8 4 12 9 14 10 10 2 14 3 12 15 7 13 13 11 16 ...

output:

177459 99321 67846 81202 116472 172856 16852 61109 105655 166775 183740 143897 36827 61208 10592 38939 168050 90292 180728 186457 166646 174794 140282 143773 101016 133359 28215 76138 91113 31057 106899 108958 67392 2957 187811 39176 174095 156645 111612 89767 184088 140473 34297 51838 28274 50141 3...

result:

ok 

Test #20:

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

input:

200000
1 1 1 2 2 3 3 3 1 4 4 1 2 5 2 3 5 3 4 3 5 4 5 6 7 5 4 5 8 6 7 8 7 3 9 9 3 10 11 6 3 6 3 12 7 5 13 14 13 12 13 14 13 3 4 15 3 8 9 2 9 5 10 1 7 11 6 10 6 4 15 12 5 5 10 5 2 11 9 7 8 3 12 6 4 12 16 14 15 17 18 2 15 13 9 15 8 7 14 7 8 19 12 20 9 10 12 6 6 11 6 11 12 7 13 14 13 9 21 15 8 10 14 15 ...

output:

66247 63097 62513 157379 69212 142627 121441 76315 19241 170657 117926 9539 19206 134186 15653 61600 123540 51885 86943 48276 93809 49412 78124 96248 151261 68711 48740 57968 177187 90335 130488 135871 91437 42330 174688 148879 38655 154550 157273 67390 29300 66483 25008 163011 85946 50689 177727 19...

result:

ok 

Test #21:

score: 0
Accepted
time: 63ms
memory: 20704kb

input:

200000
1 1 2 2 3 4 3 2 3 1 1 3 4 4 2 4 5 6 6 6 5 4 3 6 3 7 7 4 7 8 8 6 5 9 10 11 10 1 10 6 10 7 8 11 7 2 5 7 4 9 6 12 8 6 8 3 9 4 7 13 10 14 11 7 1 11 2 12 11 8 9 11 5 9 8 14 12 13 13 7 3 10 10 10 15 10 11 8 4 4 14 2 11 13 15 12 10 15 12 14 16 16 4 10 14 9 13 9 9 15 11 15 8 5 14 14 16 10 16 16 10 10...

output:

199795 18622 76489 41652 98735 199808 76635 23671 53566 18568 3612 44371 115284 90064 11641 53091 95924 171437 118606 106292 71140 48365 42191 93425 23709 162718 160736 24503 109057 164055 155934 92981 53144 158756 165681 167537 164747 1520 164168 64062 160389 100982 105400 165320 91355 11608 24762 ...

result:

ok 

Test #22:

score: 0
Accepted
time: 63ms
memory: 21000kb

input:

200000
1 1 1 2 1 2 3 4 3 4 4 5 6 7 6 2 7 5 6 8 2 6 7 8 7 3 4 9 3 7 6 4 5 2 5 8 2 10 6 7 9 3 8 4 10 8 9 11 10 5 6 8 9 11 10 1 11 9 11 3 12 12 10 10 11 13 3 7 12 8 13 4 10 8 13 14 15 9 15 16 2 7 9 9 8 6 15 10 16 11 12 3 1 17 9 10 9 11 16 4 11 12 12 13 18 14 5 5 15 16 12 4 19 17 13 18 13 11 12 16 19 20...

output:

131869 97143 17424 180823 13136 69932 113598 197320 73253 88533 80429 127805 164278 182645 129124 65584 173485 89548 128855 187281 23066 108899 158278 158726 156183 73146 76176 167202 40458 127221 95955 43140 79629 23016 60859 129214 20442 188437 72754 73637 156669 30286 127128 38867 168901 85055 11...

result:

ok 

Test #23:

score: 0
Accepted
time: 56ms
memory: 20712kb

input:

200000
1 1 2 3 4 3 3 4 3 5 5 6 4 4 3 5 4 5 5 5 4 6 7 4 8 8 9 7 10 5 7 8 2 5 10 8 11 11 10 9 6 12 10 7 9 10 11 9 13 12 10 11 11 2 3 12 8 5 9 8 6 13 9 12 12 4 5 6 11 5 13 14 13 6 12 7 5 14 7 13 13 8 4 14 15 15 9 15 15 11 13 16 16 15 10 8 10 16 17 10 18 16 6 10 9 11 5 15 16 18 10 8 12 13 11 15 12 15 19...

output:

132199 818 9330 140131 157913 122005 49557 104438 41914 195432 169400 173707 87422 79059 15415 136431 33003 93843 86780 50446 31854 68801 107514 21616 196945 111596 151967 72743 165589 48712 69412 103580 3008 47271 157794 75233 195350 169282 157313 132889 55189 174196 140032 67162 117272 131145 1691...

result:

ok 

Test #24:

score: 0
Accepted
time: 51ms
memory: 20984kb

input:

200000
1 2 3 2 3 3 4 1 4 5 2 3 4 4 5 5 4 6 7 3 5 3 6 4 5 8 9 7 8 1 4 4 2 6 7 9 5 8 8 9 9 5 4 9 4 10 2 5 2 5 11 10 5 5 6 9 12 11 6 11 7 12 7 13 8 11 13 14 10 2 8 11 1 14 12 9 9 12 15 8 3 13 14 4 14 13 16 10 15 11 9 8 16 11 15 14 4 17 18 16 9 5 12 13 9 14 15 6 10 10 19 17 12 16 11 12 13 9 19 4 6 17 14...

output:

21982 112834 194067 68201 190928 100741 190808 3842 162993 198648 14183 61839 137168 89813 117673 104090 85159 135874 148708 56335 99142 14480 129431 84179 85626 198482 199534 146163 194205 1132 44987 40989 5398 99812 102321 199276 84274 186878 106576 193237 139227 69922 22032 108955 16238 137393 36...

result:

ok 

Test #25:

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

input:

200000
1 1 2 3 4 3 1 2 4 3 2 3 4 4 2 4 2 5 5 6 3 5 4 6 5 6 7 5 8 4 3 8 7 6 6 9 9 9 10 8 5 6 7 9 10 3 7 6 4 11 12 8 8 9 8 10 13 8 11 4 3 13 10 11 5 12 12 6 7 10 8 13 6 9 14 14 9 13 15 12 15 16 15 15 13 11 12 7 10 13 14 17 9 2 7 8 15 9 1 11 15 9 13 16 10 4 10 13 17 6 9 11 5 17 10 1 6 12 18 7 4 17 11 1...

output:

165860 65537 142379 151162 192984 146752 4655 82771 192354 133826 26632 35261 106990 76521 9955 43766 8755 142249 117169 187060 22761 78047 43180 152567 54957 92945 148656 46533 174025 35681 21090 168681 131314 83977 81658 196726 176308 169133 173913 153614 43102 72263 111351 162082 168793 21051 811...

result:

ok 

Test #26:

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

input:

200000
1 1 1 2 3 4 3 3 4 1 2 1 3 2 1 3 5 6 2 4 3 4 5 5 6 7 7 5 6 7 8 4 6 9 2 7 4 8 4 5 5 8 7 4 6 9 8 7 9 9 10 8 7 8 11 9 9 11 9 12 10 9 11 10 7 6 7 13 11 4 5 12 8 12 9 13 14 10 13 14 14 15 15 15 15 12 11 11 12 11 12 10 6 7 16 13 13 9 8 9 8 7 9 8 14 14 16 17 9 9 10 11 18 12 6 7 16 13 11 12 3 17 16 11...

output:

155102 149989 39550 115971 146856 190593 146744 140493 149288 28340 98719 2461 122180 27917 957 38445 155014 186777 15346 144574 15758 53567 120197 82769 106794 186916 154018 56444 75102 107287 173059 39598 65742 190057 6551 106114 38381 137145 21461 35662 22160 121583 90927 20195 33321 172547 92288...

result:

ok 

Test #27:

score: 0
Accepted
time: 63ms
memory: 20792kb

input:

200000
1 1 1 2 3 4 5 5 6 7 2 5 3 4 6 8 6 9 1 8 5 5 5 6 9 1 7 6 2 8 5 3 4 8 9 9 8 10 5 10 9 1 5 7 2 6 2 11 7 11 8 8 12 9 6 13 2 7 10 8 9 3 11 11 10 12 2 4 9 14 4 10 11 12 13 8 15 13 10 8 14 4 9 3 15 3 4 7 13 9 16 5 10 15 1 14 5 16 14 17 11 5 15 11 12 16 3 5 17 10 18 10 19 15 13 17 13 19 5 13 12 2 5 5...

output:

108396 63850 54980 105846 133652 141883 189249 147748 156584 175312 61511 144128 92612 93406 146873 178370 144557 192991 52650 175442 124747 120156 95851 123675 180250 10542 123897 106992 46200 159866 95776 49857 52427 143689 157411 154919 140075 189379 63476 156481 154043 6044 55562 122103 30917 60...

result:

ok 

Test #28:

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

input:

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

output:

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

result:

ok 

Test #29:

score: 0
Accepted
time: 36ms
memory: 18756kb

input:

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 1...

output:

200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959 199958...

result:

ok 

Test #30:

score: 0
Accepted
time: 43ms
memory: 18696kb

input:

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

output:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177...

result:

ok 

Test #31:

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

input:

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

output:

6 3 5 1 2 8 4 7 9 10 27 24 30 26 22 29 23 25 21 28 40 52 43 49 51 47 45 46 44 42 62 63 68 72 61 70 66 64 65 67 80 86 77 89 83 79 91 82 88 85 107 110 104 106 102 103 108 100 105 109 125 131 129 122 127 119 124 126 128 121 154 151 149 146 148 143 145 141 142 144 160 157 159 162 168 166 167 169 170 164...

result:

ok 

Test #32:

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

input:

200000
1 2 3 4 1 5 6 2 2 2 5 5 3 2 4 5 6 2 6 6 7 8 9 8 9 10 10 9 8 10 11 3 4 12 5 10 4 7 8 8 9 11 2 10 8 5 12 3 10 7 10 6 11 12 8 8 13 4 8 13 12 13 14 5 3 10 12 9 15 15 15 16 16 1 7 13 10 4 5 11 6 6 6 9 12 16 14 4 13 10 12 11 16 6 5 5 14 14 6 17 18 19 20 19 21 22 20 19 21 22 23 23 24 25 20 21 26 26 ...

output:

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

result:

ok 

Test #33:

score: 0
Accepted
time: 58ms
memory: 21012kb

input:

200000
1 1 1 2 2 3 4 1 5 2 6 5 1 7 5 6 3 4 8 2 2 2 3 3 4 5 4 5 6 9 5 2 4 7 7 6 7 8 6 8 9 7 6 5 8 3 10 4 5 4 6 9 3 11 6 5 10 11 4 12 11 10 7 10 10 5 8 11 7 5 6 2 8 5 8 9 8 11 9 7 12 10 11 13 12 7 11 11 13 4 14 13 5 12 13 14 15 6 15 7 9 14 13 1 16 8 15 8 9 15 7 16 3 10 10 16 6 16 2 8 7 17 11 17 11 11 ...

output:

425 321 210 804 490 495 824 62 907 474 925 868 22 963 857 891 483 814 981 445 374 217 478 310 468 501 431 463 509 986 440 56 320 604 598 489 588 846 482 629 878 576 467 328 587 189 973 301 309 204 459 603 81 980 319 278 924 952 124 962 938 624 455 617 610 234 477 867 418 196 242 26 473 160 462 597 4...

result:

ok 

Test #34:

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

input:

200000
1 2 3 3 4 1 1 5 3 2 4 2 5 6 2 7 8 4 9 4 5 2 3 8 6 9 6 9 6 4 3 7 1 7 2 7 10 1 8 9 9 9 11 4 10 11 10 11 3 3 8 6 4 9 9 10 5 10 5 10 2 5 11 10 12 10 11 13 13 4 12 14 6 12 7 6 4 15 16 8 5 16 3 11 13 13 5 9 9 13 16 14 6 17 7 9 15 14 3 17 13 15 9 8 10 15 4 4 9 9 16 11 9 12 13 13 15 12 10 9 5 18 19 1...

output:

1549 2675 6836 6523 7085 1201 474 7483 2695 2357 4332 2111 5013 7053 1475 7452 8842 4263 9451 2812 4243 1265 2132 7482 6497 8416 4357 7511 4309 2657 1764 6401 199 4913 322 4515 8450 18 6867 7423 7335 6927 8899 2640 8381 8484 7391 8415 1053 829 5296 4282 1595 5421 5392 6803 2517 6468 1879 5907 53 174...

result:

ok 

Test #35:

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

input:

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

output:

99681 100126 100570 101013 101455 101896 102336 102775 103213 103650 104086 104521 104955 105388 105820 106251 106681 107110 107538 107965 108391 108816 109240 109663 110085 110506 110926 111345 111763 112180 112596 113011 113425 113838 114250 114661 115071 115480 115888 116295 116701 117106 117510 ...

result:

ok 

Test #36:

score: 0
Accepted
time: 49ms
memory: 19768kb

input:

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

output:

120200 120599 120997 121394 121790 122185 122579 122972 123364 123755 124145 124534 124922 125309 125695 126080 126464 126847 127229 127610 127990 128369 128747 129124 129500 129875 130249 130622 130994 131365 131735 132104 132472 132839 133205 133570 133934 134297 134659 135020 135380 135739 136097...

result:

ok 

Test #37:

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

input:

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

output:

5050 5150 5250 5350 5450 5550 5650 5750 5850 5950 6050 6150 6250 6350 6450 6550 6650 6750 6850 6950 7050 7150 7250 7350 7450 7550 7650 7750 7850 7950 8050 8150 8250 8350 8450 8550 8650 8750 8850 8950 9050 9150 9250 9350 9450 9550 9650 9750 9850 9950 10050 10150 10250 10350 10450 10550 10650 10750 10...

result:

ok 

Test #38:

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

input:

198916
1 1 2 1 2 1 2 3 2 4 1 1 1 3 2 3 4 3 3 4 1 1 5 5 2 3 5 6 7 4 2 5 2 6 1 4 3 7 4 5 4 3 1 5 8 5 2 9 4 3 2 4 3 10 6 2 1 1 8 11 9 5 1 7 8 2 2 1 12 2 3 4 5 1 9 2 6 5 4 2 6 3 7 3 5 6 7 13 7 10 14 6 15 16 11 12 17 13 6 18 3 19 3 8 1 9 10 2 7 20 1 14 1 11 12 7 4 2 8 2 4 15 1 21 22 3 3 3 16 17 2 3 4 1 3...

output:

99681 99235 100126 98790 99680 98346 99234 100570 98789 101013 97903 97461 97020 100125 98345 99679 100569 99233 98788 100124 96580 96141 101455 101012 97902 98344 100568 101896 102336 99678 97460 100123 97019 101454 95703 99232 97901 101895 98787 99677 98343 97459 95266 99231 102775 98786 96579 103...

result:

ok 

Test #39:

score: 0
Accepted
time: 59ms
memory: 20796kb

input:

200000
1 1 2 1 3 2 3 4 4 1 5 2 6 1 1 3 5 7 2 1 1 4 1 1 3 8 5 4 5 6 7 2 9 2 8 9 2 6 6 3 7 8 10 7 8 10 2 3 1 3 2 2 1 4 1 4 5 6 11 1 1 2 11 7 3 12 8 3 5 6 4 9 5 12 7 10 2 4 3 4 4 11 1 6 13 12 1 3 7 4 3 2 14 5 2 6 2 1 4 15 8 16 9 1 1 3 10 2 5 4 7 1 8 11 1 12 17 9 18 10 2 6 3 7 5 5 9 4 11 6 7 1 1 8 19 3 ...

output:

180100 179900 180299 179700 180497 180099 180298 180694 180496 179500 180890 179899 181085 179300 179100 180098 180693 181279 179699 178900 178700 180297 178500 178300 179898 181472 180495 180097 180296 180889 181084 179499 181664 179299 181278 181471 179099 180692 180494 179698 180888 181083 181855...

result:

ok 

Test #40:

score: 0
Accepted
time: 51ms
memory: 20448kb

input:

200000
1 1 1 2 1 1 2 3 3 2 3 2 4 5 3 1 2 4 1 3 5 2 3 2 1 2 3 3 4 4 4 5 6 6 5 6 4 7 5 4 4 8 1 9 7 5 5 8 10 2 5 6 1 7 3 6 11 4 2 6 9 8 3 9 12 5 10 4 5 13 10 7 11 12 6 6 11 14 12 6 8 9 7 10 6 7 15 11 12 8 16 9 7 8 9 10 13 7 8 8 7 11 8 13 13 17 18 10 19 20 11 12 12 21 9 13 13 10 22 23 7 8 24 14 11 9 9 1...

output:

55 45 36 65 28 21 54 75 64 44 53 35 85 95 43 15 27 74 10 34 84 20 26 14 6 9 19 13 63 52 42 73 105 94 62 83 33 115 51 25 18 125 3 135 104 41 32 114 145 5 24 72 1 93 8 61 155 12 2 50 124 103 4 113 165 17 134 7 11 175 123 82 144 154 40 31 133 185 143 23 92 102 71 112 16 60 195 122 132 81 205 91 49 70 8...

result:

ok 

Test #41:

score: 0
Accepted
time: 58ms
memory: 20828kb

input:

200000
1 1 1 2 1 3 1 1 1 2 3 2 1 2 2 2 4 1 2 1 5 3 1 1 1 4 1 6 5 7 2 3 3 1 8 3 1 2 1 3 3 3 1 1 6 2 3 9 10 2 11 7 2 12 3 4 5 1 8 4 6 9 1 2 13 3 1 7 4 8 14 15 4 5 3 1 4 6 5 1 9 4 10 10 5 5 5 7 2 4 8 3 16 9 11 1 4 2 5 5 6 11 2 7 8 6 2 1 1 4 10 1 4 2 9 6 12 1 7 4 10 7 8 11 2 1 13 2 3 3 3 3 4 17 9 18 3 1...

output:

80200 79800 79401 80600 79003 81000 78606 78210 77815 80199 80599 79799 77421 79400 79002 78605 81400 77028 78209 76636 81800 80198 76245 75855 75466 80999 75078 82200 81399 82600 77814 79798 79399 74691 83000 79001 74305 77420 73920 78604 78208 77813 73536 73153 81799 77027 77419 83400 83800 76635 ...

result:

ok 

Test #42:

score: 0
Accepted
time: 51ms
memory: 20500kb

input:

200000
1 1 2 2 1 3 4 2 3 1 1 4 3 4 2 2 5 1 2 3 5 6 3 5 3 6 6 1 7 7 2 7 1 1 1 4 8 1 3 2 4 2 2 8 9 4 1 3 2 8 10 5 9 2 11 12 13 10 9 10 14 5 11 3 6 12 15 11 7 12 13 6 5 16 4 1 8 5 2 1 2 1 2 7 1 14 4 17 15 13 14 16 5 6 17 7 4 5 1 18 9 10 19 18 1 19 2 2 15 3 11 16 1 2 3 2 4 1 8 6 12 1 8 2 5 7 4 3 13 5 14...

output:

199810 199790 199829 199809 199770 199847 199864 199789 199828 199750 199730 199846 199808 199827 199769 199749 199880 199710 199729 199788 199863 199895 199768 199845 199748 199879 199862 199690 199909 199894 199709 199878 199670 199650 199630 199807 199922 199610 199728 199689 199787 199669 199649...

result:

ok