| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 438400 |
2021-06-27T22:38:54 Z |
ruadhan |
Sorting (IOI15_sorting) |
C++11 |
|
212 ms |
19396 KB |
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 5;
int n, m;
vector<int> s, x, y;
vector<int> a, revA, en, revEn;
bool valid(int t)
{
a = s;
for (int i = 0; i < t; i++)
swap(a[x[i]], a[y[i]]);
for (int i = 0; i < n; i++)
revA[a[i]] = i;
int cnt = 0;
for (int i = 0; i < n; i++)
if (a[i] != i)
{
int j = revA[i];
swap(revA[a[i]], revA[a[j]]);
swap(a[i], a[j]);
cnt++;
}
return cnt <= t;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n = N, m = M;
s.resize(N), x.resize(M), y.resize(M), a.resize(N), revA.resize(N), en.resize(N), revEn.resize(N);
for (int i = 0; i < N; i++)
s.at(i) = S[i];
for (int i = 0; i < M; i++)
x.at(i) = X[i], y.at(i) = Y[i];
int R = 0;
int l = 0, r = M;
while (l != r)
{
int mid = (l + r) / 2;
if (!valid(mid))
l = mid + 1;
else
r = mid;
}
R = l;
a = s;
for (int i = 0; i < n; i++)
revA[a[i]] = i;
en = a;
for (int i = 0; i < R; i++)
swap(en[x[i]], en[y[i]]);
for (int i = 0; i < n; i++)
revEn[en[i]] = i;
queue<pair<int, int>> changes;
vector<int> tmp = en;
for (int i = 0; i < n; i++)
if (tmp[i] != i)
{
int j = revEn[i];
swap(revEn[tmp[i]], revEn[tmp[j]]);
swap(tmp[i], tmp[j]);
changes.push({i, j});
}
for (int i = 0; i < R; i++)
{
swap(revA[a[x[i]]], revA[a[y[i]]]);
swap(a[x[i]], a[y[i]]);
if (!changes.empty())
{
auto change = changes.front();
changes.pop();
P[i] = revA[en[change.first]];
Q[i] = revA[en[change.second]];
swap(en[change.first], en[change.second]);
swap(revA[a[P[i]]], revA[a[Q[i]]]);
swap(a[P[i]], a[Q[i]]);
}
else
P[i] = Q[i] = 1;
}
return R;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
1 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
204 KB |
Output is correct |
| 21 |
Correct |
1 ms |
460 KB |
Output is correct |
| 22 |
Correct |
2 ms |
460 KB |
Output is correct |
| 23 |
Correct |
2 ms |
460 KB |
Output is correct |
| 24 |
Correct |
2 ms |
460 KB |
Output is correct |
| 25 |
Correct |
2 ms |
460 KB |
Output is correct |
| 26 |
Correct |
1 ms |
460 KB |
Output is correct |
| 27 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
2 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
2 ms |
460 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
460 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
460 KB |
Output is correct |
| 8 |
Correct |
2 ms |
460 KB |
Output is correct |
| 9 |
Correct |
2 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
2 ms |
460 KB |
Output is correct |
| 12 |
Correct |
2 ms |
460 KB |
Output is correct |
| 13 |
Correct |
2 ms |
460 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
180 ms |
16576 KB |
Output is correct |
| 16 |
Correct |
190 ms |
16956 KB |
Output is correct |
| 17 |
Correct |
210 ms |
17848 KB |
Output is correct |
| 18 |
Correct |
81 ms |
13892 KB |
Output is correct |
| 19 |
Correct |
164 ms |
16640 KB |
Output is correct |
| 20 |
Correct |
160 ms |
17204 KB |
Output is correct |
| 21 |
Correct |
166 ms |
17332 KB |
Output is correct |
| 22 |
Correct |
171 ms |
18088 KB |
Output is correct |
| 23 |
Correct |
210 ms |
18424 KB |
Output is correct |
| 24 |
Correct |
211 ms |
18172 KB |
Output is correct |
| 25 |
Correct |
208 ms |
17964 KB |
Output is correct |
| 26 |
Correct |
164 ms |
17332 KB |
Output is correct |
| 27 |
Correct |
150 ms |
16556 KB |
Output is correct |
| 28 |
Correct |
199 ms |
19396 KB |
Output is correct |
| 29 |
Correct |
194 ms |
18640 KB |
Output is correct |
| 30 |
Correct |
128 ms |
15684 KB |
Output is correct |
| 31 |
Correct |
196 ms |
19068 KB |
Output is correct |
| 32 |
Correct |
196 ms |
17848 KB |
Output is correct |
| 33 |
Correct |
190 ms |
18264 KB |
Output is correct |
| 34 |
Correct |
206 ms |
18220 KB |
Output is correct |
| 35 |
Correct |
159 ms |
16568 KB |
Output is correct |
| 36 |
Correct |
69 ms |
15040 KB |
Output is correct |
| 37 |
Correct |
212 ms |
18624 KB |
Output is correct |
| 38 |
Correct |
205 ms |
17916 KB |
Output is correct |
| 39 |
Correct |
205 ms |
17984 KB |
Output is correct |
