oj.uz

Submission #1085630

# Submission time Handle Problem Language Result Execution time Memory
1085630 2024-09-08T13:54:11 Z guagua0407 Sorting (IOI15_sorting) C++17
100 / 100
 190 ms 25736 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
 
// 0 1 2    0 1 2
//          0   2
// 0 1      0 1
//   1 2
// 1 2 0    1 2 0
 
vector<pii> ans;
 
void dfs(int u, vector<int> &p, vector<int> &vis)
{
	vis[u] = 1;
	if (!vis[p[u]])
	{
		ans.emplace_back(pii(u, p[u]));
		dfs(p[u], p, vis);
	}
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	auto check = [&](int K)
	{
		vector<int> v(N), vis(N, 0), pos(N);
		ans.clear();
		for (int i = 0; i < N; i++)
			v[i] = S[i];
		for (int i = 0; i < K; i++)
			swap(v[X[i]], v[Y[i]]);
		for (int i = 0; i < N; i++)
			if (!vis[i])
				dfs(i, v, vis);
		if(ans.size() <= K)
		{
			reverse(ans.begin(), ans.end());
			while(ans.size() <= K)
				ans.emplace_back(pii(0, 0));
			for(int i = 0; i < N; i++)
				pos[i] = i, v[i] = i;
			for(int i = K - 1; i >= 0; i--)
			{
				P[i] = pos[ans[i].F];
				Q[i] = pos[ans[i].S];
				tie(v[X[i]], v[Y[i]], pos[v[X[i]]], pos[v[Y[i]]]) = make_tuple(v[Y[i]], v[X[i]], pos[v[Y[i]]], pos[v[X[i]]]);
			}
			return true;
		}
		else 
			return false;
	};
	int L = 0, R = M;
	while(L < R)
	{
		int mid = (L + R) / 2;
		if(check(mid))
			R = mid;
		else 
			L = mid + 1;
	}
	check(L);
	return L;
}

Compilation message

sorting.cpp: In lambda function:
sorting.cpp:41:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if(ans.size() <= K)
      |      ~~~~~~~~~~~^~~~
sorting.cpp:44: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]
   44 |    while(ans.size() <= K)
      |          ~~~~~~~~~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 356 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 1 ms 356 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 432 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 140 ms 23452 KB Output is correct
16 Correct 158 ms 22888 KB Output is correct
17 Correct 176 ms 24040 KB Output is correct
18 Correct 82 ms 20416 KB Output is correct
19 Correct 154 ms 22976 KB Output is correct
20 Correct 152 ms 23528 KB Output is correct
21 Correct 147 ms 24408 KB Output is correct
22 Correct 131 ms 19016 KB Output is correct
23 Correct 158 ms 25428 KB Output is correct
24 Correct 176 ms 24524 KB Output is correct
25 Correct 178 ms 24040 KB Output is correct
26 Correct 156 ms 24632 KB Output is correct
27 Correct 138 ms 23556 KB Output is correct
28 Correct 169 ms 24508 KB Output is correct
29 Correct 176 ms 23804 KB Output is correct
30 Correct 117 ms 21928 KB Output is correct
31 Correct 185 ms 24240 KB Output is correct
32 Correct 149 ms 24164 KB Output is correct
33 Correct 185 ms 23968 KB Output is correct
34 Correct 174 ms 24792 KB Output is correct
35 Correct 156 ms 22468 KB Output is correct
36 Correct 62 ms 22720 KB Output is correct
37 Correct 190 ms 25736 KB Output is correct
38 Correct 174 ms 23584 KB Output is correct
39 Correct 178 ms 24544 KB Output is correct