# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
228661 |
2020-05-02T09:42:09 Z |
pit4h |
Sorting (IOI15_sorting) |
C++14 |
|
206 ms |
29660 KB |
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int dfs(int x, vector<int>& g, vector<bool>& vis) {
vis[x]=1;
if(!vis[g[x]]) {
return dfs(g[x], g, vis)+1;
}
return 1;
}
void dfsv(int x, vector<int>& g, vector<bool>& vis, vector<int>& vec) {
vis[x]=1;
vec.push_back(x);
if(!vis[g[x]]) {
dfsv(g[x], g, vis, vec);
}
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
vector<int> t;
for(int i=0; i<n; ++i) {
t.push_back(s[i]);
}
int lo = 0, hi = m, len=m;
while(lo<=hi) {
int l = (lo+hi)/2;
vector<bool> vis(n);
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
for(int i=0; i<l; ++i) {
swap(t[x[i]], t[y[i]]);
}
int cnt=0;
for(int i=0; i<n; ++i) {
if(!vis[i]) {
cnt += dfs(i, t, vis)-1;
}
}
if(cnt<=l) {
len=l;
hi=l-1;
}
else {
lo=l+1;
}
}
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
for(int i=0; i<len; ++i) {
swap(t[x[i]], t[y[i]]);
}
vector<int> wrong, pos(n), T=t, POS(n);
vector<bool> vis(n);
for(int i=0; i<n; ++i) {
if(t[i]!=i && !vis[i]) {
vector<int> vec;
dfsv(i, t, vis, vec);
reverse(vec.begin(), vec.end());
for(int j: vec) wrong.push_back(t[j]);
}
pos[s[i]]=i;
POS[t[i]]=i;
}
for(int i=0; i<n; ++i) {
t[i]=s[i];
}
for(int i=0; i<len; ++i) {
p[i]=q[i]=0;
}
reverse(wrong.begin(), wrong.end());
for(int i=0; i<len; ++i) {
swap(t[x[i]], t[y[i]]);
swap(pos[t[x[i]]], pos[t[y[i]]]);
while(wrong.size() && T[wrong.back()]==wrong.back()) { // update
wrong.pop_back();
}
if(wrong.empty()) break;
int u = wrong.back();
wrong.pop_back();
p[i]=pos[u];
q[i]=pos[T[u]];
swap(t[p[i]], t[q[i]]);
swap(pos[t[p[i]]], pos[t[q[i]]]);
swap(T[POS[u]], T[u]); // zamień miejscami gościa z wartością 'u' i gościa, który na końcu jest na pozycji 'u'
swap(POS[u], POS[T[u]]);
}
return len;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
128 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
128 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
4 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
256 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
256 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
128 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
4 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
256 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
256 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
256 KB |
Output is correct |
14 |
Correct |
4 ms |
256 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
256 KB |
Output is correct |
19 |
Correct |
5 ms |
256 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
512 KB |
Output is correct |
22 |
Correct |
5 ms |
512 KB |
Output is correct |
23 |
Correct |
5 ms |
512 KB |
Output is correct |
24 |
Correct |
5 ms |
512 KB |
Output is correct |
25 |
Correct |
6 ms |
688 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
6 ms |
512 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
640 KB |
Output is correct |
14 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
6 ms |
512 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
6 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
6 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
640 KB |
Output is correct |
14 |
Correct |
5 ms |
512 KB |
Output is correct |
15 |
Correct |
165 ms |
19824 KB |
Output is correct |
16 |
Correct |
174 ms |
25016 KB |
Output is correct |
17 |
Correct |
193 ms |
23092 KB |
Output is correct |
18 |
Correct |
81 ms |
16496 KB |
Output is correct |
19 |
Correct |
163 ms |
19180 KB |
Output is correct |
20 |
Correct |
173 ms |
19820 KB |
Output is correct |
21 |
Correct |
173 ms |
19820 KB |
Output is correct |
22 |
Correct |
157 ms |
18388 KB |
Output is correct |
23 |
Correct |
194 ms |
25856 KB |
Output is correct |
24 |
Correct |
197 ms |
26476 KB |
Output is correct |
25 |
Correct |
191 ms |
22740 KB |
Output is correct |
26 |
Correct |
173 ms |
19692 KB |
Output is correct |
27 |
Correct |
159 ms |
19308 KB |
Output is correct |
28 |
Correct |
195 ms |
27256 KB |
Output is correct |
29 |
Correct |
197 ms |
19568 KB |
Output is correct |
30 |
Correct |
128 ms |
18924 KB |
Output is correct |
31 |
Correct |
189 ms |
19820 KB |
Output is correct |
32 |
Correct |
184 ms |
25932 KB |
Output is correct |
33 |
Correct |
195 ms |
22660 KB |
Output is correct |
34 |
Correct |
184 ms |
19940 KB |
Output is correct |
35 |
Correct |
162 ms |
18928 KB |
Output is correct |
36 |
Correct |
75 ms |
17648 KB |
Output is correct |
37 |
Correct |
206 ms |
29660 KB |
Output is correct |
38 |
Correct |
201 ms |
28412 KB |
Output is correct |
39 |
Correct |
197 ms |
28664 KB |
Output is correct |