#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5;
int N, M, ans;
int S[MAXN+10], X[MAXN+10], Y[MAXN+10], *P, *Q;
int A[MAXN+10], B[MAXN+10], T[MAXN+10];
bool vis[MAXN+10];
bool solve(int R)
{
for(int i=1; i<=N; i++) A[i]=S[i];
for(int i=1; i<=R; i++)
{
swap(A[X[i]], A[Y[i]]);
}
vector<pii> V;
for(int i=1; i<=N; i++) vis[i]=false;
//for(int i=1; i<=N; i++) printf("%d ", A[i]); printf("\n");
for(int i=1; i<=N; i++)
{
if(vis[i]) continue;
for(int now=i; ; now=A[now])
{
vis[now]=true;
if(vis[A[now]]) break;
V.push_back({A[now], A[A[now]]});
//printf("!%d %d\n", A[now], A[A[now]]);
}
}
if(V.size()>R) return false;
for(int i=1; i<=N; i++) T[i]=i, A[i]=i;
for(int i=1; i<=R; i++) P[i]=Q[i]=1;
for(int i=R; i>=1; i--)
{
//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");
if(!V.empty())
{
pii t=V.back(); V.pop_back();
pii a=pii(T[t.first], T[t.second]);
P[i]=a.first; Q[i]=a.second;
swap(A[a.first], A[a.second]);
swap(T[t.first], T[t.second]);
}
//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");
pii a=pii(X[i], Y[i]);
pii t=pii(A[a.first], A[a.second]);
swap(A[a.first], A[a.second]);
swap(T[t.first], T[t.second]);
}
//for(int j=1; j<=N; j++) printf("%d ", A[j]); printf("\n");
for(int i=0; i<R; i++)
{
P[i]=P[i+1]-1;
Q[i]=Q[i+1]-1;
}
return true;
}
int findSwapPairs(int _N, int _S[], int _M, int _X[], int _Y[], int _P[], int _Q[])
{
N=_N; M=_M; P=_P; Q=_Q;
for(int i=1; i<=N; i++) S[i]=_S[i-1]+1;
for(int i=1; i<=M; i++) X[i]=_X[i-1]+1, Y[i]=_Y[i-1]+1;
int lo=0, hi=M;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(solve(mid)) hi=mid;
else lo=mid;
}
for(int i=0; i<hi; i++)
{
swap(_S[_X[i]], _S[_Y[i]]);
swap(_S[Q[i]], _S[P[i]]);
}
//for(int i=0; i<N; i++) printf("%d ", _S[i]);
for(int i=0; i<N; i++) assert(i==_S[i]);
return hi;
}
Compilation message
sorting.cpp: In function 'bool solve(int)':
sorting.cpp:39:13: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
39 | if(V.size()>R) return false;
| ~~~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid=lo+hi>>1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
620 KB |
Output is correct |
3 |
Correct |
2 ms |
620 KB |
Output is correct |
4 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
620 KB |
Output is correct |
3 |
Correct |
2 ms |
620 KB |
Output is correct |
4 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |