# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
778271 | boris_mihov | Sorting (IOI15_sorting) | C++17 | 158 ms | 23628 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 "sorting.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
typedef long long llong;
const int MAXN = 200000 + 10;
const int INF = 1e9;
int n;
int p[MAXN];
int pos[MAXN];
bool vis[MAXN];
std::vector <std::pair <int,int>> ops;
std::stack <std::pair <int,int>> st;
void getOps()
{
ops.clear();
std::fill(vis + 1, vis + 1 + n, false);
for (int i = 1 ; i <= n ; ++i)
{
if (vis[i])
{
continue;
}
while (!st.empty())
{
st.pop();
}
int curr = i;
while (!vis[curr])
{
vis[curr] = true;
curr = p[curr];
if (!vis[curr])
{
st.push({p[curr], p[i]});
}
}
while (!st.empty())
{
ops.push_back(st.top());
st.pop();
}
}
}
void makeSwap(int x, int y)
{
std::swap(p[x], p[y]);
pos[p[x]] = x;
pos[p[y]] = y;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n = N;
for (int i = 1 ; i <= n ; ++i)
{
p[i] = S[i - 1] + 1;
}
getOps();
if (ops.empty())
{
return 0;
}
int l = 0, r = M + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
for (int i = 1 ; i <= n ; ++i)
{
p[i] = S[i - 1] + 1;
}
for (int i = 1 ; i <= mid ; ++i)
{
std::swap(p[X[i - 1] + 1], p[Y[i - 1] + 1]);
}
getOps();
if (ops.size() <= mid) r = mid;
else l = mid;
}
for (int i = 1 ; i <= n ; ++i)
{
p[i] = S[i - 1] + 1;
}
for (int i = 1 ; i <= r ; ++i)
{
std::swap(p[X[i - 1] + 1], p[Y[i - 1] + 1]);
}
getOps();
while (ops.size() < r)
{
ops.push_back({1, 1});
}
for (int i = 1 ; i <= n ; ++i)
{
p[i] = S[i - 1] + 1;
pos[p[i]] = i;
}
for (int i = 0 ; i < ops.size() ; ++i)
{
makeSwap(X[i] + 1, Y[i] + 1);
P[i] = pos[ops[i].first] - 1;
Q[i] = pos[ops[i].second] - 1;
makeSwap(P[i] + 1, Q[i] + 1);
}
for (int i = 1 ; i <= n ; ++i)
{
assert(p[i] == i);
}
return ops.size();
}
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... |