oj.uz

Submission #17290

# Submission time Handle Problem Language Result Execution time Memory
17290 2015-11-12T17:14:30 Z erdemkiraz Sorting (IOI15_sorting) C++
100 / 100
 638 ms 17752 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 4 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1280 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 4 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1280 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 3 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 3 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 4 ms 1280 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 4 ms 1152 KB Output is correct
5 Correct 3 ms 1280 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 3 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 3 ms 1152 KB Output is correct
14 Correct 4 ms 1152 KB Output is correct
15 Correct 4 ms 1280 KB Output is correct
16 Correct 3 ms 1152 KB Output is correct
17 Correct 3 ms 1152 KB Output is correct
18 Correct 3 ms 1152 KB Output is correct
19 Correct 4 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 1408 KB Output is correct
23 Correct 5 ms 1452 KB Output is correct
24 Correct 4 ms 1408 KB Output is correct
25 Correct 4 ms 1408 KB Output is correct
26 Correct 5 ms 1408 KB Output is correct
27 Correct 4 ms 1408 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 5 ms 1280 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 1 ms 1280 KB Output is correct
8 Correct 5 ms 1408 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 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 6 ms 1280 KB Output is correct
2 Correct 5 ms 1280 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 1 ms 1280 KB Output is correct
8 Correct 5 ms 1408 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1280 KB Output is correct
12 Correct 5 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 442 ms 16088 KB Output is correct
16 Correct 502 ms 16372 KB Output is correct
17 Correct 556 ms 16784 KB Output is correct
18 Correct 88 ms 12396 KB Output is correct
19 Correct 302 ms 13728 KB Output is correct
20 Correct 373 ms 16376 KB Output is correct
21 Correct 375 ms 16124 KB Output is correct
22 Correct 563 ms 17064 KB Output is correct
23 Correct 550 ms 17752 KB Output is correct
24 Correct 638 ms 17028 KB Output is correct
25 Correct 468 ms 16940 KB Output is correct
26 Correct 362 ms 15452 KB Output is correct
27 Correct 325 ms 13892 KB Output is correct
28 Correct 502 ms 16808 KB Output is correct
29 Correct 606 ms 15888 KB Output is correct
30 Correct 295 ms 13608 KB Output is correct
31 Correct 593 ms 16212 KB Output is correct
32 Correct 475 ms 16904 KB Output is correct
33 Correct 517 ms 16892 KB Output is correct
34 Correct 519 ms 16420 KB Output is correct
35 Correct 280 ms 13680 KB Output is correct
36 Correct 64 ms 12024 KB Output is correct
37 Correct 456 ms 17476 KB Output is correct
38 Correct 350 ms 17008 KB Output is correct
39 Correct 441 ms 17024 KB Output is correct