# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
278167 | davitmarg | Sorting (IOI15_sorting) | C++17 | 3 ms | 640 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.
/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 200005;
#ifndef death
#include "sorting.h"
#endif
int x[N], y[N], s[N],a[N], pos[N],f[N],g[N];
int n, m;
vector<pair<int, int>> ans;
void add(int x, int y, bool sw = 1)
{
if(sw)
ans.push_back(MP(x, y));
else
{
swap(g[x], g[y]);
f[g[x]] = x;
f[g[y]] = y;
}
swap(a[x], a[y]);
pos[a[x]] = x;
pos[a[y]] = y;
}
bool check(int k)
{
ans.clear();
for (int i = 0; i < n; i++)
{
a[i] = s[i];
f[i] = i;
pos[s[i]] = i;
}
for (int i = 0; i < k; i++)
swap(f[x[i]], f[y[i]]);
for (int i = 0; i < n; i++)
g[f[i]] = i;
int last = 0;
for (int i = 0; i < k; i++)
{
add(x[i], y[i],0);
while (last < n && pos[last] == f[last])
last++;
if (last >= n)
{
ans.push_back(MP(0, 0));
continue;
}
add(pos[last], f[last]);
last++;
}
return (last >= n);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n = N;
m = M;
for (int i = 0; i < n; i++)
s[i] = S[i];
for (int i = 0; i < m; i++)
{
x[i] = X[i];
y[i] = Y[i];
}
check(m);
for (int i = 0; i < ans.size(); i++)
{
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return ans.size();
}
#ifdef death
int nn, mm,ss[N], xx[N], yy[N], pp[N], qq[N];
int main()
{
fastIO;
cin >> nn >> mm;
for (int i = 0; i < nn; i++)
cin >> ss[i];
for (int i = 0; i < mm; i++)
cin >> xx[i] >> yy[i];
mm=findSwapPairs(nn, ss, mm, xx, yy, pp, qq);
for (int i = 0; i < mm; i++)
{
swap(ss[xx[i]], ss[yy[i]]);
swap(ss[pp[i]], ss[qq[i]]);
}
cout << endl;
for (int i = 0; i < nn; i++)
cout << ss[i] << " ";
cout << endl;
return 0;
}
#endif
/*
5 5
3 0 4 2 1
1 1
4 0
2 3
1 4
0 4
10 8
0 1 2 3 4 5 6 7 9 8
8 9
4 0
2 3
1 4
0 4
8 9
7 8
5 7
*/
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... |