oj.uz

Submission #1019275

# Submission time Handle Problem Language Result Execution time Memory
1019275 2024-07-10T16:45:48 Z parsadox2 Sorting (IOI15_sorting) C++17
100 / 100
 123 ms 34752 KB 
#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int N = 2e5 + 10 , M = 6e5 + 10;
int n , ar[N] , pos[N] , m , L[M] , R[M] , f[M] , s[M];
vector <pair<int , int>> vec;

bool Check(int mid)
{
	for(int i = 0 ; i < mid ; i++)
		swap(ar[L[i]] , ar[R[i]]);
	for(int i = 0 ; i < n ; i++)
		pos[ar[i]] = i;
	vec.clear();
	for(int i = 0 ; i < n ; i++)  if(ar[i] != i)
	{
		int p = pos[i];
		swap(ar[i] , ar[p]);
		pos[ar[p]] = p;
		pos[ar[i]] = i;
		vec.push_back(make_pair(ar[i] , ar[p]));
	}
	return (vec.size() <= mid);
}

void Solve(int mid)
{
	if(vec.size() < mid)
		vec.push_back(make_pair(0 , 0));
	for(int i = 0 ; i < mid ; i++)
	{
		swap(ar[L[i]] , ar[R[i]]);
		swap(pos[ar[L[i]]] , pos[ar[R[i]]]);
		f[i] = pos[vec[i].F];
		s[i] = pos[vec[i].S];
		swap(ar[f[i]] , ar[s[i]]);
		swap(pos[ar[f[i]]] , pos[ar[s[i]]]);
	}
}

int findSwapPairs(int nn, int S[], int mm, int X[], int Y[], int P[], int Q[]) {
	n = nn;
	m = mm;
	for(int i = 0 ; i < m ; i++)
	{
		L[i] = X[i];
		R[i] = Y[i];
	}
	int low = -1 , high = m;
	while(high - low > 1)
	{
		for(int i = 0 ; i < n ; i++)
		{
			ar[i] = S[i];
			pos[ar[i]] = i;
		}
		int mid = (low + high) >> 1;
		if(Check(mid))
			high = mid;
		else
			low = mid;
	}
	for(int i = 0 ; i < n ; i++)
	{
		ar[i] = S[i];
		pos[ar[i]] = i;
	}
	Check(high);
	for(int i = 0 ; i < n ; i++)
	{
		ar[i] = S[i];
		pos[ar[i]] = i;
	}
	Solve(high);
	for(int i = 0 ; i < m ; i++)
	{
		P[i] = f[i];
		Q[i] = s[i];
	}
	return high;
}

Compilation message

sorting.cpp: In function 'bool Check(int)':
sorting.cpp:28:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |  return (vec.size() <= mid);
      |          ~~~~~~~~~~~^~~~~~
sorting.cpp: In function 'void Solve(int)':
sorting.cpp:33:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |  if(vec.size() < mid)
      |     ~~~~~~~~~~~^~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 8780 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 2 ms 8656 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 105 ms 31572 KB Output is correct
16 Correct 119 ms 32212 KB Output is correct
17 Correct 115 ms 30148 KB Output is correct
18 Correct 62 ms 25796 KB Output is correct
19 Correct 93 ms 32568 KB Output is correct
20 Correct 91 ms 33216 KB Output is correct
21 Correct 92 ms 33272 KB Output is correct
22 Correct 91 ms 28864 KB Output is correct
23 Correct 101 ms 34240 KB Output is correct
24 Correct 115 ms 32356 KB Output is correct
25 Correct 118 ms 33512 KB Output is correct
26 Correct 90 ms 32712 KB Output is correct
27 Correct 84 ms 31944 KB Output is correct
28 Correct 123 ms 33668 KB Output is correct
29 Correct 110 ms 33160 KB Output is correct
30 Correct 76 ms 31276 KB Output is correct
31 Correct 105 ms 33680 KB Output is correct
32 Correct 113 ms 33320 KB Output is correct
33 Correct 117 ms 33984 KB Output is correct
34 Correct 116 ms 33732 KB Output is correct
35 Correct 84 ms 32192 KB Output is correct
36 Correct 45 ms 27732 KB Output is correct
37 Correct 116 ms 34752 KB Output is correct
38 Correct 115 ms 33476 KB Output is correct
39 Correct 122 ms 33660 KB Output is correct