oj.uz

Submission #16564

# Submission time Handle Problem Language Result Execution time Memory
16564 2015-08-28T04:33:10 Z gs14004 Sorting (IOI15_sorting) C++14
100 / 100
 784 ms 13816 KB 
#include "sorting.h"
#include <algorithm>
using namespace std;

int *s, *x, *y, *p, *q, n;
int obj[200005], cur[200005];
int orev[200005], crev[200005];

bool trial(int t){
	for(int i=0; i<n; i++){
		obj[i] = i;
	}
	for(int i=t-1; i>=0; i--){
		swap(obj[x[i]], obj[y[i]]);
	}
	for(int i=0; i<n; i++){
		orev[obj[i]] = i;
		cur[i] = s[i];
		crev[cur[i]] = i;
	}
	int pt = 0;
	for(int i=0; i<t; i++){
		swap(obj[x[i]], obj[y[i]]);
		swap(cur[x[i]], cur[y[i]]);
		crev[cur[x[i]]] = x[i];
		orev[obj[x[i]]] = x[i];
		crev[cur[y[i]]] = y[i];
		orev[obj[y[i]]] = y[i];
		while(pt < n && crev[pt] == orev[pt]) pt++;
		if(pt == n){
			p[i] = q[i] = 0;
			continue;
		}
		int p1 = crev[pt];
		int p2 = orev[pt];
		p[i] = p1;
		q[i] = p2;
		swap(cur[p1], cur[p2]);
		crev[cur[p1]] = p1;
		crev[cur[p2]] = p2;
	}
	while(pt < n && crev[pt] == orev[pt]) pt++;
	return (pt == n);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N, s = S, x = X, y = Y, p = P, q = Q;
	int s = 0, e = M;
	while(s != e){
		int m = (s+e)/2;
		if(trial(m)) e = m;
		else s = m+1;
	}
	trial(s);
	return s;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:48:6: warning: declaration of 's' shadows a global declaration [-Wshadow]
  int s = 0, e = M;
      ^
sorting.cpp:5:6: note: shadowed declaration is here
 int *s, *x, *y, *p, *q, n;
      ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 556 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 420 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 345 ms 12260 KB Output is correct
16 Correct 431 ms 12668 KB Output is correct
17 Correct 694 ms 13316 KB Output is correct
18 Correct 138 ms 10452 KB Output is correct
19 Correct 414 ms 12240 KB Output is correct
20 Correct 390 ms 12636 KB Output is correct
21 Correct 516 ms 12664 KB Output is correct
22 Correct 423 ms 13404 KB Output is correct
23 Correct 449 ms 13744 KB Output is correct
24 Correct 695 ms 13456 KB Output is correct
25 Correct 639 ms 13396 KB Output is correct
26 Correct 417 ms 12688 KB Output is correct
27 Correct 387 ms 12176 KB Output is correct
28 Correct 676 ms 13304 KB Output is correct
29 Correct 508 ms 13048 KB Output is correct
30 Correct 302 ms 11796 KB Output is correct
31 Correct 565 ms 13480 KB Output is correct
32 Correct 390 ms 13360 KB Output is correct
33 Correct 583 ms 13432 KB Output is correct
34 Correct 527 ms 13508 KB Output is correct
35 Correct 337 ms 12084 KB Output is correct
36 Correct 64 ms 11256 KB Output is correct
37 Correct 784 ms 13816 KB Output is correct
38 Correct 527 ms 13404 KB Output is correct
39 Correct 549 ms 13432 KB Output is correct