oj.uz

Submission #302041

# Submission time Handle Problem Language Result Execution time Memory
302041 2020-09-18T11:37:03 Z Berted Sorting (IOI15_sorting) C++14
100 / 100
 298 ms 36484 KB 
#include "sorting.h"
#include <vector>
#include <iostream>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

int N, A[200001], T[200001], pos[200001]; 
pii S[600001];
bool vis[200001];
vector<int> check;

void DFS(int u)
{
	if (!vis[u])
	{
		vis[u] = 1;
		check.push_back(u);
		DFS(T[u]);
	}
}

vector<pii> getSwaps(int x)
{
	vector<pii> ret;
	for (int i = 0; i < N; i++) {T[i] = A[i]; vis[i] = 0;}
	for (int i = 0; i < x; i++) {swap(T[S[i].fst], T[S[i].snd]);}
	for (int i = 0; i < N; i++)
	{
		DFS(i);
		for (int i = 1; i < check.size(); i++) {ret.push_back({check[i - 1], check[i]});}
		check.clear();
	}
	return ret;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) 
{
	::N = N;
	for (int i = 0; i < N; i++) {A[i] = S[i]; pos[A[i]] = i;}
	for (int i = 0; i < M; i++) {::S[i] = {X[i], Y[i]};}

	int L = 0, R = M;
	while (L < R)
	{
		int M = L + R >> 1;
		if (getSwaps(M).size() <= M) {R = M;}
		else {L = M + 1;}
	}	

	vector<pii> V = getSwaps(L);
	//for (auto &x : V) {cerr << x.fst << ", " << x.snd << "\n";}

	for (int i = 0; i < L; i++)
	{
		swap(pos[A[X[i]]], pos[A[Y[i]]]);
		swap(A[X[i]], A[Y[i]]);
		if (i < V.size())
		{
			P[i] = pos[V[i].fst]; Q[i] = pos[V[i].snd];
			swap(A[pos[V[i].fst]], A[pos[V[i].snd]]);
			swap(pos[V[i].fst], pos[V[i].snd]);
		}
		else {P[i] = Q[i] = 0;}
	}

	return L;
}

Compilation message

sorting.cpp: In function 'std::vector<std::pair<int, int> > getSwaps(int)':
sorting.cpp:33:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   33 |   for (int i = 1; i < check.size(); i++) {ret.push_back({check[i - 1], check[i]});}
      |            ^
sorting.cpp:30:11: note: shadowed declaration is here
   30 |  for (int i = 0; i < N; i++)
      |           ^
sorting.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for (int i = 1; i < check.size(); i++) {ret.push_back({check[i - 1], check[i]});}
      |                   ~~^~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:39:76: warning: declaration of 'S' shadows a global declaration [-Wshadow]
   39 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                                                            ^
sorting.cpp:11:5: note: shadowed declaration is here
   11 | pii S[600001];
      |     ^
sorting.cpp:39:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   39 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                                                            ^
sorting.cpp:10:5: note: shadowed declaration is here
   10 | int N, A[200001], T[200001], pos[200001];
      |     ^
sorting.cpp:48:7: warning: declaration of 'int M' shadows a parameter [-Wshadow]
   48 |   int M = L + R >> 1;
      |       ^
sorting.cpp:39:39: note: shadowed declaration is here
   39 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                   ~~~~^
sorting.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int M = L + R >> 1;
      |           ~~^~~
sorting.cpp:49:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |   if (getSwaps(M).size() <= M) {R = M;}
      |       ~~~~~~~~~~~~~~~~~~~^~~~
sorting.cpp:60:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if (i < V.size())
      |       ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 251 ms 29396 KB Output is correct
16 Correct 265 ms 30204 KB Output is correct
17 Correct 258 ms 34952 KB Output is correct
18 Correct 104 ms 26852 KB Output is correct
19 Correct 197 ms 29296 KB Output is correct
20 Correct 205 ms 28500 KB Output is correct
21 Correct 206 ms 30516 KB Output is correct
22 Correct 252 ms 23672 KB Output is correct
23 Correct 294 ms 33620 KB Output is correct
24 Correct 292 ms 33084 KB Output is correct
25 Correct 261 ms 34712 KB Output is correct
26 Correct 209 ms 24764 KB Output is correct
27 Correct 188 ms 24020 KB Output is correct
28 Correct 298 ms 31944 KB Output is correct
29 Correct 267 ms 25828 KB Output is correct
30 Correct 152 ms 22892 KB Output is correct
31 Correct 271 ms 26424 KB Output is correct
32 Correct 285 ms 32220 KB Output is correct
33 Correct 260 ms 35176 KB Output is correct
34 Correct 275 ms 26716 KB Output is correct
35 Correct 198 ms 28316 KB Output is correct
36 Correct 81 ms 21624 KB Output is correct
37 Correct 262 ms 36484 KB Output is correct
38 Correct 256 ms 35680 KB Output is correct
39 Correct 264 ms 35500 KB Output is correct