| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 20225 | 2016-04-25T02:27:08 Z | newtonis | Sorting (IOI15_sorting) | C++ | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000;
const int maxm = 600000;
int n , m;
int s[maxn];
int x[maxm];
int y[maxm];
int p[maxm]; //the answer
int q[maxm];
bool valid(int w){ //w moves
// cout << "trying "<<w<<" " << "turns" << '\n';
int cp[maxn], f[maxn] , cf[maxm], cs[maxm] , e[maxn] , fp[maxn] , pz[maxn];
for (int i = 0;i < n;i++){
cp[i] = s[i]; //copy all values
cs[i] = s[i]; //copy all values
e[s[i]] = i; //position of value s[i]
}
for (int i = 0;i < w;i++){
//cout << "initial swapping " << x[i] << ' ' << y[i] << '\n';
swap( cp[x[i] ] , cp[y[i]]); //make the swap
}
for (int i = 0;i < n;i++){ //f[value] = index where that value will end.
pz[cp[i]] = i; //where is each value at end
}
for (int i = 0;i < n;i++){
f[i] = pz[s[i]];
fp[pz[s[i]]] = i; //fp[x] = y, means that f[y]=x
}
int number = 0; //next index to correct
for (int i = 0;i < w;i++){ //for each move
swap ( f[x[i]] , f[y[i]] ); //swap f
fp[ f[x[i]] ] = x[i];
fp[ f[y[i]] ] = y[i];
swap ( cs[x[i]], cs[y[i]]); //swap cs
// update e array
e[cs[x[i]]] = x[i]; //set a value
e[cs[y[i]]] = y[i];
// f[i] is where i will end
bool end = false;
while (not end and number < n){
int index = fp[number]; //this means f[index]=number
// i need to correct f[index]
//cout << "number = " << number << " , " << "index = " << index << '\n';
if (cs[index] != number){ //if the value of f[index] is not index
int a = fp[number];
int b = e[number];
swap ( cs[a] , cs[b]);
p[ i ] = a;
q[ i ] = b;
e[cs[a]] = a;
e[cs[b]] = b;
//cout << "advance " << "swap " << "("<<a<<','<<b<<")"<< '\n';
end = true;
}
number ++;
}
if (not end){
p[i] = 0; //set no move
q[i] = 0;
}
}
/*cout << "final = ";
for (int i = 0;i < n;i++){
cout << cs[i] << ',';
}
cout << '\n';*/
for (int i = 0;i < n;i++){
if (cs[i] != i){
return false;
}
}
return true;
/*cout << "number = " << number << '\n';
if (number == n){
return true;
}*/
//return false;
}
int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w+",stdout);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 0;i < n;i++){
cin >> s[i];
}
cin >> m;
for (int i = 0;i < m;i++){
cin >> x[i] >> y[i];
}
int a = -1;
int b = m+1;
while (a+1 != b){
int h = (a+b)/2;
//cout << "binary search " << a << ' ' << h << ' ' << b << '\n';
if (valid(h)){
b = h;
}else{
a = h;
}
}
//cout << "binary search " << a << ' ' << b << '\n';
valid(b);
cout << b << '\n';
for (int i = 0;i < b;i++){
cout << p[i] << ' ' << q[i] << '\n';
}
}