oj.uz

Submission #210939

# Submission time Handle Problem Language Result Execution time Memory
210939 2020-03-19T02:52:25 Z autumn_eel Sorting (IOI15_sorting) C++14
100 / 100
 417 ms 22004 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

int s[300000],spos[300000];
int p[300000],ppos[300000];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	if(is_sorted(S,S+N))return 0;
	auto C=[&](int R){
		rep(i,N)p[i]=i,s[i]=S[i];
		for(int i=R-1;i>=0;i--){
			swap(p[X[i]],p[Y[i]]);
		}
		rep(i,N){
			ppos[p[i]]=i;
			spos[s[i]]=i;
		}
		int g=0;
		rep(i,R){
			swap(p[X[i]],p[Y[i]]);
			swap(ppos[p[X[i]]],ppos[p[Y[i]]]);
			swap(s[X[i]],s[Y[i]]);
			swap(spos[s[X[i]]],spos[s[Y[i]]]);
			while(g<N&&spos[g]==ppos[g])g++;
			if(g==N){
				P[i]=Q[i]=0;continue;
			}
			int a=spos[g],b=ppos[g];
			P[i]=a;Q[i]=b;
			swap(s[a],s[b]);
			swap(spos[s[a]],spos[s[b]]);
		}
		rep(i,N)assert(p[i]==i);
		rep(i,N){
			if(s[i]!=i)return false;
		}
		return true;
	};
	int ok=N,ng=0;
	while(ok-ng>1){
		int R=(ok+ng)/2;
		if(C(R))ok=R;
		else ng=R;
	}
	C(ok);
	return ok;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:9:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 11 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 256 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 7 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 6 ms 512 KB Output is correct
23 Correct 6 ms 512 KB Output is correct
24 Correct 6 ms 512 KB Output is correct
25 Correct 6 ms 512 KB Output is correct
26 Correct 5 ms 512 KB Output is correct
27 Correct 5 ms 512 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 243 ms 11768 KB Output is correct
16 Correct 298 ms 19832 KB Output is correct
17 Correct 390 ms 20872 KB Output is correct
18 Correct 49 ms 13432 KB Output is correct
19 Correct 232 ms 19320 KB Output is correct
20 Correct 277 ms 20344 KB Output is correct
21 Correct 263 ms 20344 KB Output is correct
22 Correct 230 ms 16272 KB Output is correct
23 Correct 241 ms 21752 KB Output is correct
24 Correct 417 ms 21496 KB Output is correct
25 Correct 393 ms 21116 KB Output is correct
26 Correct 256 ms 19960 KB Output is correct
27 Correct 233 ms 19420 KB Output is correct
28 Correct 387 ms 21224 KB Output is correct
29 Correct 387 ms 20728 KB Output is correct
30 Correct 174 ms 18936 KB Output is correct
31 Correct 363 ms 21112 KB Output is correct
32 Correct 267 ms 20996 KB Output is correct
33 Correct 402 ms 21496 KB Output is correct
34 Correct 316 ms 21368 KB Output is correct
35 Correct 239 ms 19060 KB Output is correct
36 Correct 87 ms 18296 KB Output is correct
37 Correct 403 ms 22004 KB Output is correct
38 Correct 411 ms 21264 KB Output is correct
39 Correct 380 ms 21240 KB Output is correct