oj.uz

Submission #362611

# Submission time Handle Problem Language Result Execution time Memory
362611 2021-02-03T17:51:27 Z NachoLibre Sorting (IOI15_sorting) C++17
100 / 100
 296 ms 33184 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "sorting.h"
#else
#endif

const int N = 200005, M = 600005;
int n, m, s[N], x[M], y[M], c[N], d[N];

inline void S(int x, int y) {
	d[c[x]] = y;
	d[c[y]] = x;
	swap(c[x], c[y]);
}

void Gc() {
	for(int i = 0; i < n; ++i) {
		c[i] = s[i];
		d[s[i]] = i;
	}
}

vector<pair<int, int>> C(int a) {
	vector<pair<int, int>> dr(1, {0, 0});
	Gc();
	for(int i = 0; i < a; ++i) {
		S(x[i], y[i]);
	}
	for(int i = 0; i < n; ++i) {
		if(c[i] != i) {
			if(sz(dr) == a + 1) {
				dr[0].first = 12321;
				break;
			}
			dr.push_back({i, c[i]});
			S(i, d[i]);
		}
	}
	while(dr.size() < a + 1) {
		dr.push_back({0, 0});
	}
	return dr;
}

vector<pair<int, int>> D(vector<pair<int, int>> v) {
	vector<pair<int, int>> dr;
	Gc();
	for(int i = 1; i < sz(v); ++i) {
		S(x[i - 1], y[i - 1]);
		dr.push_back({d[v[i].first], d[v[i].second]});
		S(d[v[i].first], d[v[i].second]);
	}
	return dr;
}

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) {
		x[i] = _x[i];
		y[i] = _y[i];
	}
	int l = 0, r = m;
	while(l < r) {
		int md = (l + r) / 2;
		if(C(md)[0].first) {
			l = md + 1;
		} else {
			r = md;
		}
	}
	vector<pair<int, int>> ve = C(l);
	vector<pair<int, int>> mo = D(ve);
	for(int i = 0; i < sz(mo); ++i) {
		p[i] = mo[i].first;
		q[i] = mo[i].second;
	}
	return sz(mo);
}

#ifdef wambule
int nn = 5;
int mm = 5;
int ss[] = {3, 0, 4, 2, 1};
int xx[] = {1, 4, 2, 1, 0};
int yy[] = {1, 0, 3, 4, 4};
int p[M], q[M];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int k = findSwapPairs(nn, ss, mm, xx, yy, p, q);
	cout << k << endl;
	for(int i = 0; i < k; ++i) {
		cout << p[i] << " " << q[i] << endl;
	}
	return 0;
}
#endif

Compilation message

sorting.cpp: In function 'void S(int, int)':
sorting.cpp:13:27: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   13 | inline void S(int x, int y) {
      |                           ^
sorting.cpp:11:23: note: shadowed declaration is here
   11 | int n, m, s[N], x[M], y[M], c[N], d[N];
      |                       ^
sorting.cpp:13:27: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   13 | inline void S(int x, int y) {
      |                           ^
sorting.cpp:11:17: note: shadowed declaration is here
   11 | int n, m, s[N], x[M], y[M], c[N], d[N];
      |                 ^
sorting.cpp: In function 'std::vector<std::pair<int, int> > C(int)':
sorting.cpp:42:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  while(dr.size() < a + 1) {
      |        ~~~~~~~~~~^~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 205 ms 29356 KB Output is correct
16 Correct 237 ms 30100 KB Output is correct
17 Correct 296 ms 31380 KB Output is correct
18 Correct 91 ms 24156 KB Output is correct
19 Correct 204 ms 26836 KB Output is correct
20 Correct 205 ms 27552 KB Output is correct
21 Correct 212 ms 27808 KB Output is correct
22 Correct 203 ms 26864 KB Output is correct
23 Correct 237 ms 32784 KB Output is correct
24 Correct 293 ms 31968 KB Output is correct
25 Correct 279 ms 31616 KB Output is correct
26 Correct 210 ms 27552 KB Output is correct
27 Correct 190 ms 26700 KB Output is correct
28 Correct 281 ms 31708 KB Output is correct
29 Correct 277 ms 31160 KB Output is correct
30 Correct 155 ms 25692 KB Output is correct
31 Correct 276 ms 31552 KB Output is correct
32 Correct 231 ms 31444 KB Output is correct
33 Correct 290 ms 32100 KB Output is correct
34 Correct 262 ms 32012 KB Output is correct
35 Correct 207 ms 26368 KB Output is correct
36 Correct 75 ms 25692 KB Output is correct
37 Correct 295 ms 33184 KB Output is correct
38 Correct 291 ms 31616 KB Output is correct
39 Correct 288 ms 31856 KB Output is correct