| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 65482 |
2018-08-07T17:44:07 Z |
hamzqq9 |
Sorting (IOI15_sorting) |
C++14 |
|
282 ms |
14584 KB |
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define MAX 200005
int go[MAX],plc[MAX],_S[MAX],vis[MAX];
int get_val(int N) {
int res=0;
fill(vis,vis+N,0);
for(int i=0;i<N;i++) {
if(!vis[i]) {
int cur=i;
int sz=0;
while(!vis[cur]) {
vis[cur]=1;
sz++;
cur=go[cur];
}
res+=sz-1;
}
}
return res;
}
void do_swap(int upto,int X[],int Y[]) {
for(int i=0;i<upto;i++) swap(_S[X[i]],_S[Y[i]]);
}
void build_graph(int N) {
for(int i=0;i<N;i++) plc[_S[i]]=i;
for(int i=0;i<N;i++) go[plc[i]]=i;
}
bool okey(int N,int upto,int S[],int X[],int Y[]) {
for(int i=0;i<N;i++) _S[i]=S[i];
do_swap(upto,X,Y);
build_graph(N);
return get_val(N)<=upto;
}
void get_ans(int N,int upto,int P[],int Q[],int X[],int Y[],int S[]) {
fill(vis,vis+N,0);
int tot=0;
pair<int,int> swp[MAX];
for(int i=0;i<N;i++) {
if(!vis[i]) {
int cur=i;
while(!vis[cur]) {
vis[cur]=1;
if(go[cur]!=i) {
swp[tot++]={_S[cur],_S[go[cur]]};
}
cur=go[cur];
}
}
}
for(int i=0;i<N;i++) plc[S[i]]=i;
for(int i=0;i<tot;i++) {
swap(plc[S[X[i]]],plc[S[Y[i]]]);
swap(S[X[i]],S[Y[i]]);
P[i]=plc[swp[i].first];
Q[i]=plc[swp[i].second];
swap(plc[S[P[i]]],plc[S[Q[i]]]);
swap(S[P[i]],S[Q[i]]);
}
while(tot<upto) {
P[tot]=Q[tot]=0;
tot++;
}
}
void find_solution(int N,int upto,int S[],int X[],int Y[],int P[],int Q[]) {
for(int i=0;i<N;i++) _S[i]=S[i];
do_swap(upto,X,Y);
build_graph(N);
get_ans(N,upto,P,Q,X,Y,S);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int bas=0,son=M;
while(bas<=son) {
if(okey(N,orta,S,X,Y)) son=orta-1;
else bas=orta+1;
}
int ans=bas;
find_solution(N,ans,S,X,Y,P,Q);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1892 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1892 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 22 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 23 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 24 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 25 |
Correct |
6 ms |
2048 KB |
Output is correct |
| 26 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 27 |
Correct |
5 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 13 |
Correct |
6 ms |
2048 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 4 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 12 |
Correct |
5 ms |
2048 KB |
Output is correct |
| 13 |
Correct |
6 ms |
2048 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2048 KB |
Output is correct |
| 15 |
Correct |
192 ms |
12380 KB |
Output is correct |
| 16 |
Correct |
214 ms |
12796 KB |
Output is correct |
| 17 |
Correct |
268 ms |
13620 KB |
Output is correct |
| 18 |
Correct |
80 ms |
9848 KB |
Output is correct |
| 19 |
Correct |
208 ms |
12256 KB |
Output is correct |
| 20 |
Correct |
245 ms |
12536 KB |
Output is correct |
| 21 |
Correct |
278 ms |
12664 KB |
Output is correct |
| 22 |
Correct |
225 ms |
13404 KB |
Output is correct |
| 23 |
Correct |
230 ms |
13688 KB |
Output is correct |
| 24 |
Correct |
256 ms |
13688 KB |
Output is correct |
| 25 |
Correct |
280 ms |
13916 KB |
Output is correct |
| 26 |
Correct |
255 ms |
12408 KB |
Output is correct |
| 27 |
Correct |
212 ms |
12024 KB |
Output is correct |
| 28 |
Correct |
269 ms |
13432 KB |
Output is correct |
| 29 |
Correct |
218 ms |
13488 KB |
Output is correct |
| 30 |
Correct |
143 ms |
11512 KB |
Output is correct |
| 31 |
Correct |
222 ms |
13688 KB |
Output is correct |
| 32 |
Correct |
238 ms |
13220 KB |
Output is correct |
| 33 |
Correct |
268 ms |
13948 KB |
Output is correct |
| 34 |
Correct |
246 ms |
13688 KB |
Output is correct |
| 35 |
Correct |
238 ms |
12280 KB |
Output is correct |
| 36 |
Correct |
71 ms |
10488 KB |
Output is correct |
| 37 |
Correct |
282 ms |
14584 KB |
Output is correct |
| 38 |
Correct |
278 ms |
13892 KB |
Output is correct |
| 39 |
Correct |
276 ms |
14332 KB |
Output is correct |
