#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define MAX 200005
int go[MAX],plc[MAX],_S[MAX],vis[MAX];
int get_val(int N) {
int res=0;
fill(vis,vis+N,0);
for(int i=0;i<N;i++) {
if(!vis[i]) {
int cur=i;
int sz=0;
while(!vis[cur]) {
vis[cur]=1;
sz++;
cur=go[cur];
}
res+=sz-1;
}
}
return res;
}
void do_swap(int upto,int X[],int Y[]) {
for(int i=0;i<upto;i++) swap(_S[X[i]],_S[Y[i]]);
}
void build_graph(int N) {
for(int i=0;i<N;i++) plc[_S[i]]=i;
for(int i=0;i<N;i++) go[plc[i]]=i;
}
bool okey(int N,int upto,int S[],int X[],int Y[]) {
for(int i=0;i<N;i++) _S[i]=S[i];
do_swap(upto,X,Y);
build_graph(N);
return get_val(N)<=upto;
}
void get_ans(int N,int upto,int P[],int Q[],int X[],int Y[],int S[]) {
fill(vis,vis+N,0);
int tot=0;
pair<int,int> swp[MAX];
for(int i=0;i<N;i++) {
if(!vis[i]) {
int cur=i;
while(!vis[cur]) {
vis[cur]=1;
if(go[cur]!=i) {
swp[tot++]={_S[cur],_S[go[cur]]};
}
cur=go[cur];
}
}
}
for(int i=0;i<N;i++) plc[S[i]]=i;
for(int i=0;i<tot;i++) {
swap(plc[S[X[i]]],plc[S[Y[i]]]);
swap(S[X[i]],S[Y[i]]);
P[i]=plc[swp[i].first];
Q[i]=plc[swp[i].second];
}
while(tot<upto) {
P[tot]=Q[tot]=0;
tot++;
}
}
void find_solution(int N,int upto,int S[],int X[],int Y[],int P[],int Q[]) {
for(int i=0;i<N;i++) _S[i]=S[i];
do_swap(upto,X,Y);
build_graph(N);
get_ans(N,upto,P,Q,X,Y,S);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int bas=0,son=M;
while(bas<=son) {
if(okey(N,orta,S,X,Y)) son=orta-1;
else bas=orta+1;
}
int ans=bas;
find_solution(N,ans,S,X,Y,P,Q);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1920 KB |
Output is correct |
2 |
Correct |
4 ms |
1920 KB |
Output is correct |
3 |
Correct |
4 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1920 KB |
Output is correct |
5 |
Incorrect |
4 ms |
1920 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1920 KB |
Output is correct |
2 |
Correct |
4 ms |
1920 KB |
Output is correct |
3 |
Correct |
4 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1920 KB |
Output is correct |
5 |
Incorrect |
4 ms |
1920 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1920 KB |
Output is correct |
2 |
Incorrect |
4 ms |
1920 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1920 KB |
Output is correct |
2 |
Correct |
4 ms |
1920 KB |
Output is correct |
3 |
Correct |
4 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1920 KB |
Output is correct |
5 |
Incorrect |
4 ms |
1920 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2048 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |