| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 60180 | Flugan42 | 정렬하기 (IOI15_sorting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sorting.h"
#include <bits/stdc++.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9223372036854775807
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
ll lo = -1, hi = N, mid;
while (lo+1 < hi){
mid = (lo+hi)/2;
vi last; last.assign(N,0);
rep(i,0,N) last[i] = S[i];
rep(i,0,mid){
ll t1 = last[X[i]];
ll t2 = last[Y[i]];
last[Y[i]] = t1;
last[X[i]] = t2;
}
vi inv; inv.assign(N,0);
rep(i,0,N) inv[last[i]] = i;
ll cur = 0;
rep(i,0,mid){
while (cur < N && inv[cur] == cur) cur++;
if (cur == N) break;
ll s = last[cur],ls = inv[cur];
last[ls] = s;
last[cur] = cur;
inv[cur] = cur;
inv[s] = ls;
}
if (inv[N-1] != N-1) {
lo = mid;
} else {
hi = mid;
}
}
if (hi == 0){
bool check = true;
rep(i,0,N) if (S[i] != i) check = false;
if (check) return 0;
else hi = 1;
}
vi last; last.assign(N,0);
rep(i,0,N) last[i] = S[i];
rep(i,0,hi){
ll t1 = last[X[i]];
ll t2 = last[Y[i]];
last[Y[i]] = t1;
last[X[i]] = t2;
}
vi inv; inv.assign(N,0);
rep(i,0,N) inv[last[i]] = i;
ll cur = 0;
vii swap;
rep(i,0,hi){
while (cur < N && inv[cur] == cur) cur++;
if (cur == N) break;
ll s = last[cur],ls = inv[cur];
swap.push_back(make_pair(s,cur));
last[ls] = s;
last[cur] = cur;
inv[cur] = cur;
inv[s] = ls;
}
while (sz(swap) < hi) swap.push_back(make_pair(0,0));
last.assign(N,0);
inv.assign(N,0);
rep(i,0,N) last[i] = S[i];
rep(i,0,N) inv[last[i]] = i;
rep(i,0,hi){
ll t1 = last[X[i]];
ll t2 = last[Y[i]];
last[Y[i]] = t1;
last[X[i]] = t2;
inv[t1] = Y[i];
inv[t2] = X[i];
//
P[i] = inv[swap[i].first];
Q[i] = inv[swap[i].second];
last[P[i]] = swap[i].second;
last[Q[i]] = swap[i].first;
inv[swap[i].first] = Q[i];
inv[swap[i].second] = P[i];
}
return hi;
}
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main()
{
_inputFile = fopen("sorting.in", "rb");
_outputFile = fopen("sorting.out", "w");
int N, M;
N = _readInt();
int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
for (int i = 0; i < N; ++i)
S[i] = _readInt();
M = _readInt();
int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
for (int i = 0; i < M; ++i) {
X[i] = _readInt();
Y[i] = _readInt();
}
int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
int ans = findSwapPairs(N, S, M, X, Y, P, Q);
fprintf(_outputFile, "%d\n", ans);
for (int i = 0; i < ans; ++i)
fprintf(_outputFile, "%d %d\n", P[i], Q[i]);
return 0;
}