| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 257855 | shrek12357 | Sorting (IOI15_sorting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "sorting.h"
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll H = 1e6 + 11;
//ifstream in(".in");
//ofstream out(".out");
int pos[H], n, m;
pi query[H], ans[H], a[H];
vector<pair<int, int>> toChange;
vector<int> xAns, yAns;
bool check(int mid, int nums[], int n, int x[], int y[]) {
int in[n + 11], out[n + 11];
for(int i = 0; i < n; i++){
in[i] = out[i] = nums[i];
}
for(int i = 0; i < mid; i++){
swap(out[query[i].first], out[query[i].second]);
}
for (int i = 0; i < mid; i++) {
int a = nums[x[i]];
nums[x[i]] = nums[y[i]];
nums[y[i]] = a;
}
int adjList[n + 5]; // can optimize later
for (int i = 0; i < n; i++) {
adjList[i] = nums[i];
}
int counter = 0;
bool viz[n + 5];
for (int i = 0; i < n; i++) {
viz[i] = false;
}
int k = 0;
for(int i = 0; i < n; i++){
if(viz[i])continue;
vector<int>cur;
int v = out[i];
while(v != i){
cur.push_back(v);
v = out[v];
}
cur.push_back(v);
for(int j = sz(cur) - 1; j > 0; j--){
a[k++] = {cur[0], cur[j]};
}
for(auto it : cur)viz[it] = 1;
}
if(k > mid) return false;
for (int i = 0; i < n; ++i){
pos[in[i]] = i;
}
for(int i = 0; i < k; i++){
//His move
int x = query[i].ff, y = query[i].ss;
swap(in[x], in[y]);
pos[in[x]] = x;
pos[in[y]] = y;
//My move
x = pos[a[i].ff], y = pos[a[i].ss];
swap(in[x], in[y]);
pos[in[x]] = x;
pos[in[y]] = y;
ans[i] = {x, y};
}
while(k < t)ans[k++] = {0, 0};
return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int lo = -1;
int hi = M;
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (check(mid,S,N,X,Y)) {
hi = mid;
}
else {
lo = mid;
}
toChange.clear();
}
check(hi, S, N, X, Y);
getAns(hi, S, N, X, Y);
for (int i = 0; i < xAns.size(); i++) {
P[i] = xAns[i];
Q[i] = yAns[i];
}
return hi;
}