# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
387248 | alireza_kaviani | Sorting (IOI15_sorting) | C++11 | 929 ms | 35808 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define SZ(x) int((x).size())
const int MAXN = 2e5 + 10;
int A[MAXN] , to[MAXN] , pos[MAXN] , mark[MAXN] , p[MAXN] , q[MAXN];
vector<int> vec , adj[MAXN];
void DFS(int v){
mark[v] = 1;
vec.push_back(v);
// cout << v << endl;
for(int u : adj[v]){
// cout << v << ' ' << u << endl;
if(!mark[u]) DFS(u);
}
}
int check(int N, int M, int X[], int Y[]) {
// cout << endl << "==========" << endl << M << endl;
int cnt = 0;
fill(p , p + MAXN , 0);
fill(q , q + MAXN , 0);
fill(mark , mark + MAXN , 0);
for(int i = 0 ; i < N ; i++) adj[i].clear();
for(int i = 0 ; i < N ; i++) to[i] = pos[i] = i;
for(int i = 0 ; i < M ; i++){
swap(A[X[i]] , A[Y[i]]);
}
for(int i = 0 ; i < N ; i++){
// cout << A[i] << ' ';
adj[i].push_back(A[i]);
}
// cout << endl;
for(int i = 0 ; i < N ; i++){
if(!mark[i]){
vec.clear();
DFS(i);
// cout << "DFS " << i << ' ' << SZ(vec) << endl;
// for(int j : vec) cout << j << ' ';
for(int j = 1 ; j < SZ(vec) ; j++){
if(cnt == M) return 0;
p[cnt] = vec[0];
q[cnt] = vec[j];
// cout << vec[0] << ' ' << vec[j] << endl;
cnt++;
}
// cout << endl;
}
}
for(int i = M - 1 ; i >= 0 ; i--){
if(i < cnt){
p[i] = to[p[i]];
q[i] = to[q[i]];
}
to[pos[X[i]]] = Y[i];
to[pos[Y[i]]] = X[i];
swap(pos[X[i]] , pos[Y[i]]);
}
return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int l = -1 , r = N;
while(r - l > 1){
int mid = l + r >> 1;
for(int i = 0 ; i < N ; i++) A[i] = S[i];
if(check(N , mid , X , Y)) r = mid;
else l = mid;
}
for(int i = 0 ; i < N ; i++) A[i] = S[i];
int tmp = check(N , r , X , Y);
for(int i = 0 ; i < r ; i++){
P[i] = p[i];
Q[i] = q[i];
}
return r;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |