## Submission #129541

# Submission time Handle Problem Language Result Execution time Memory
129541 2019-07-12T13:15:47 Z Meloric Sorting (IOI15_sorting) C++14
0 / 100
1000 ms 524292 KB
```#include "sorting.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()

using namespace std;
vector<vector<pii>> g;
vector<vector<pii>> ind;

vector<int> give(int time){
vector<int> ans;
for(int i = 0; i< g.size(); i++){
int l = -1;
int r = g[i].size()-1;
while(r-l>1){
int m = (r+l)/2;
if(g[i][m].X >= time)r = m;
else l = m;
}
ans.pb(g[i][r].Y);
}
return ans;
}
void dfs(int v, vector<int>& cur, vector<int>& vis){
if(vis[v])return;
vis[v] = 1;
dfs(cur[v], cur, vis);
}
int cycles(vector<int>& cur){
vector<int> vis;
vis.assign(cur.size(), 0);
int ans = 0;
for(int i = 0; i< cur.size(); i++){
if(!vis[i]){
ans++;
dfs(i, cur, vis);
}
}
return ans;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int flag = 0;
for(int i = 0; i< N; i++){
if(S[i]!=i)flag = 1;
}
if(!flag)return 0;
g.assign(N, vector<pii>());
ind.assign(N, vector<pii>());

for(int i = 0; i< N; i++){
g[i].pb({0, S[i]});
ind[S[i]].pb({0, i});
}
for(int i = 0; i < M; i++){
int nx, ny;
nx = g[X[i]].back().Y;
ny = g[Y[i]].back().Y;
g[X[i]].pb({i+1, ny});
g[Y[i]].pb({i+1, nx});
ind[nx].pb({i+1, Y[i]});
ind[ny].pb({i+1, X[i]});
}
int l = 0; int r = M;
while(r-l>1){
int m = (r+l)/2;
vector<int> cur = give(m);
if(N-cycles(cur)<=m)r = m;
else l = m;
}
vector<int> cur = give(r);
vector<pii> swp;
for(int i = 0; i < cur.size(); i++){
while(cur[i]!=i){
swp.pb({cur[i], cur[cur[i]]});
int a = cur[i]; int b = cur[cur[i]];
cur[i] = b; cur[cur[i]] = a;
}
}
int ans = r;
for(int i = 0; i< r; i++){
int ia, ib;
ia = swp[i].X; ib = swp[i].Y;
l = 0; r = ind[ia].size();
while(r-l>1){
int m = (r+l)/2;
if(i+1<ind[ia][m].X)r = m;
else l = m;
}
int fa, fb;
fa = l;
l = 0; r = ind[ib].size();
while(r-l>1){
int m = (r+l)/2;
if(i+1<ind[ib][m].X)r = m;
else l = m;
}
fb = l;
P[i] = fb;
Q[i] = fa;
}
return ans;
}
```

### Compilation message

```sorting.cpp: In function 'std::vector<int> give(int)':
sorting.cpp:16:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< g.size(); i++){
~^~~~~~~~~~
sorting.cpp:18:28: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int r = g[i].size()-1;
~~~~~~~~~~~^~
sorting.cpp: In function 'int cycles(std::vector<int>&)':
sorting.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< cur.size(); i++){
~^~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < cur.size(); i++){
~~^~~~~~~~~~~~
sorting.cpp:87:32: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
l = 0; r = ind[ia].size();
~~~~~~~~~~~~^~
sorting.cpp:95:32: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
l = 0; r = ind[ib].size();
~~~~~~~~~~~~^~```

#### Subtask #1 0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 1010 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

#### Subtask #2 0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 1010 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

#### Subtask #3 0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 1002 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

#### Subtask #4 0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 1010 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

#### Subtask #5 0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1008 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

#### Subtask #6 0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1008 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -