#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int maxn = 2e5+10;
const int maxm = 6e5+10;
typedef pair<int, int> pii;
int s[maxn], final[maxn], pos[maxn], pos_final[maxn];
// checa se S está ordenado
bool check(int N)
{
for (int i = 0; i < N; i++)
if (s[i] != i) return false;
return true;
}
// Faz a operação de trocar os índices
void replace(int i, int j, bool q)
{
int a, b;
if (q)
{
a = s[i], b = s[j];
s[i] = b, s[j] = a;
pos[a] = j, pos[b] = i;
}
else
{
a = final[i], b = final[j];
final[i] = b, final[j] = a;
pos_final[a] = j, pos_final[b] = i;
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
for (int i = 0; i < N; i++)
final[i] = s[i] = S[i], pos_final[s[i]] = pos[s[i]] = i;
if (check(N)) return 0;
int ini = 1, fim = N+1, ans = N+1;
vector<int> curP(M), curQ(M);
while (ini <= fim)
{
int mid = (ini+fim)>>1;
for (int i = 0; i < N; i++)
final[i] = s[i] = S[i], pos_final[s[i]] = pos[s[i]] = i;
for (int i = 0; i < mid; i++)
replace(X[i], Y[i], 0);
int first = 0;
for (int j = 0; j < mid; j++)
{
replace(X[j], Y[j], 1);
for (int i = first; i < N; i++)
{
if (final[i] == i)
{
first++;
curP[j] = curQ[j] = 0;
continue;
}
curP[j] = pos[i], curQ[j] = pos[final[i]];
replace(curP[j], curQ[j], 1);
replace(pos_final[i], i, 0);
first++;
break;
}
}
if (check(N))
{
fim = mid-1, ans = mid;
for (int i = 0; i < ans; i++)
P[i] = curP[i], Q[i] = curQ[i];
}
else ini = mid+1;
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
356 KB |
Output is correct |
| 14 |
Correct |
3 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
3 ms |
384 KB |
Output is correct |
| 17 |
Correct |
2 ms |
384 KB |
Output is correct |
| 18 |
Correct |
3 ms |
384 KB |
Output is correct |
| 19 |
Correct |
3 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
384 KB |
Output is correct |
| 21 |
Correct |
3 ms |
640 KB |
Output is correct |
| 22 |
Correct |
3 ms |
640 KB |
Output is correct |
| 23 |
Correct |
4 ms |
768 KB |
Output is correct |
| 24 |
Correct |
4 ms |
640 KB |
Output is correct |
| 25 |
Correct |
3 ms |
640 KB |
Output is correct |
| 26 |
Correct |
4 ms |
640 KB |
Output is correct |
| 27 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
4 ms |
512 KB |
Output is correct |
| 8 |
Correct |
4 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
512 KB |
Output is correct |
| 10 |
Correct |
3 ms |
512 KB |
Output is correct |
| 11 |
Correct |
4 ms |
512 KB |
Output is correct |
| 12 |
Correct |
4 ms |
512 KB |
Output is correct |
| 13 |
Correct |
3 ms |
512 KB |
Output is correct |
| 14 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
3 ms |
512 KB |
Output is correct |
| 7 |
Correct |
4 ms |
512 KB |
Output is correct |
| 8 |
Correct |
4 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
512 KB |
Output is correct |
| 10 |
Correct |
3 ms |
512 KB |
Output is correct |
| 11 |
Correct |
4 ms |
512 KB |
Output is correct |
| 12 |
Correct |
4 ms |
512 KB |
Output is correct |
| 13 |
Correct |
3 ms |
512 KB |
Output is correct |
| 14 |
Correct |
3 ms |
512 KB |
Output is correct |
| 15 |
Correct |
365 ms |
21076 KB |
Output is correct |
| 16 |
Correct |
508 ms |
21624 KB |
Output is correct |
| 17 |
Correct |
568 ms |
22952 KB |
Output is correct |
| 18 |
Correct |
47 ms |
16376 KB |
Output is correct |
| 19 |
Correct |
290 ms |
22904 KB |
Output is correct |
| 20 |
Correct |
282 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
297 ms |
23720 KB |
Output is correct |
| 22 |
Correct |
317 ms |
18236 KB |
Output is correct |
| 23 |
Correct |
417 ms |
23864 KB |
Output is correct |
| 24 |
Correct |
558 ms |
23320 KB |
Output is correct |
| 25 |
Correct |
570 ms |
23104 KB |
Output is correct |
| 26 |
Correct |
388 ms |
23316 KB |
Output is correct |
| 27 |
Correct |
345 ms |
22904 KB |
Output is correct |
| 28 |
Correct |
539 ms |
23416 KB |
Output is correct |
| 29 |
Correct |
520 ms |
23208 KB |
Output is correct |
| 30 |
Correct |
273 ms |
23024 KB |
Output is correct |
| 31 |
Correct |
552 ms |
23588 KB |
Output is correct |
| 32 |
Correct |
357 ms |
22952 KB |
Output is correct |
| 33 |
Correct |
614 ms |
23544 KB |
Output is correct |
| 34 |
Correct |
452 ms |
23348 KB |
Output is correct |
| 35 |
Correct |
261 ms |
22396 KB |
Output is correct |
| 36 |
Correct |
57 ms |
22980 KB |
Output is correct |
| 37 |
Correct |
560 ms |
24184 KB |
Output is correct |
| 38 |
Correct |
490 ms |
23160 KB |
Output is correct |
| 39 |
Correct |
479 ms |
23160 KB |
Output is correct |
