oj.uz

Submission #17291

# Submission time Handle Problem Language Result Execution time Memory
17291 2015-11-12T17:15:23 Z erdemkiraz Sorting (IOI15_sorting) C++
100 / 100
 632 ms 17800 KB 
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "sorting.h"

const int N = 2e5 + 5;

int n, m;
int s[N], a[N], h[N], w[N], p[N];
ii XY[N];

void swp(int x, int y) {
	int X = a[x];
	int Y = a[y];
	swap(w[X], w[Y]);
	swap(a[x], a[y]);
}

bool f(int x, int P[], int Q[]) {
	for(int i = 0; i < n; i++) {
		p[i] = i;
	}
	for(int i = 0; i < x; i++) {
		swap(p[XY[i].first], p[XY[i].second]);
	}
	for(int i = 0; i < n; i++) {
		w[s[i]] = i;
		a[i] = s[p[i]];
	}
	memset(h, 0, sizeof(h));
	int res = n, sz = 0;
	vector < int > v;
	vector < ii > ans;
	for(int i = 0; i < n; i++) {
		if(!h[i]) {
			res--;
			int x = i;
			v.clear();
			do{
				v.push_back(x);
				h[x] = 1;
				x = a[x];
			}while(x != i);
			for(int it = (int) v.size() - 1; it >= 1; it--) {
				int x = v[0];
				int y = v[it];
				ans.push_back(ii(a[x], a[y]));
			}
		}
	}
	for(int i = 0; i < n; i++)
		a[i] = s[i];
	if(res <= x) {
		for(int it = 0; it < ans.size(); it++) {
			swp(XY[it].first, XY[it].second);
			P[sz] = w[ans[it].first];
			Q[sz] = w[ans[it].second];
			sz++;
			swp(w[ans[it].first], w[ans[it].second]);
		}
		while(sz < x) {
			P[sz] = 0;
			Q[sz] = 0;
			sz++;
		}
		return 1;
	}
	return 0;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	m = M;
	for(int i = 0; i < n; i++)
		s[i] = S[i];
	for(int i = 0; i < m; i++) {
		XY[i] = ii(X[i], Y[i]);
	}
	int l = 0, r = n - 1;
	while(l < r) {
		int m = (l + r) >> 1;
		if(f(m, P, Q))
			r = m;
		else
			l = m + 1;
	}
	f(l, P, Q);
	return l;
}

Compilation message

sorting.cpp: In function 'bool f(int, int*, int*)':
sorting.cpp:46:8: warning: declaration of 'int x' shadows a parameter [-Wshadow]
    int x = i;
        ^
sorting.cpp:28:12: note: shadowed declaration is here
 bool f(int x, int P[], int Q[]) {
            ^
sorting.cpp:54:9: warning: declaration of 'x' shadows a previous local [-Wshadow]
     int x = v[0];
         ^
sorting.cpp:46:8: note: shadowed declaration is here
    int x = i;
        ^
sorting.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int it = 0; it < ans.size(); it++) {
                   ~~~^~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:80:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                                                            ^
sorting.cpp:15:11: note: shadowed declaration is here
 const int N = 2e5 + 5;
           ^
sorting.cpp:90:7: warning: declaration of 'm' shadows a global declaration [-Wshadow]
   int m = (l + r) >> 1;
       ^
sorting.cpp:17:8: note: shadowed declaration is here
 int n, m;
        ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1408 KB Output is correct
2 Correct 5 ms 1408 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 5 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct
11 Correct 5 ms 1408 KB Output is correct
12 Correct 4 ms 1408 KB Output is correct
13 Correct 5 ms 1280 KB Output is correct
14 Correct 4 ms 1280 KB Output is correct
15 Correct 416 ms 15948 KB Output is correct
16 Correct 375 ms 16188 KB Output is correct
17 Correct 530 ms 16944 KB Output is correct
18 Correct 88 ms 12524 KB Output is correct
19 Correct 230 ms 13860 KB Output is correct
20 Correct 274 ms 16476 KB Output is correct
21 Correct 336 ms 16184 KB Output is correct
22 Correct 361 ms 16840 KB Output is correct
23 Correct 580 ms 17800 KB Output is correct
24 Correct 624 ms 17064 KB Output is correct
25 Correct 560 ms 17072 KB Output is correct
26 Correct 431 ms 15404 KB Output is correct
27 Correct 421 ms 13888 KB Output is correct
28 Correct 611 ms 16760 KB Output is correct
29 Correct 541 ms 15912 KB Output is correct
30 Correct 272 ms 13656 KB Output is correct
31 Correct 632 ms 16124 KB Output is correct
32 Correct 552 ms 16664 KB Output is correct
33 Correct 565 ms 16916 KB Output is correct
34 Correct 447 ms 16288 KB Output is correct
35 Correct 362 ms 13600 KB Output is correct
36 Correct 63 ms 12024 KB Output is correct
37 Correct 533 ms 17288 KB Output is correct
38 Correct 418 ms 17004 KB Output is correct
39 Correct 411 ms 16968 KB Output is correct