# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
68696 |
2018-08-18T07:51:33 Z |
MANcity |
Sorting (IOI15_sorting) |
C++14 |
|
311 ms |
13308 KB |
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "sorting.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int t[200002];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int u=0;
for0(i,N-1)
if(S[i]!=i)
u=1;
if(u==0)
return 0;
int l=0;
int r=(M-1);
while(1)
{
if(l==r)
{
pair<int,int> NS[200002];
int pos[200002];
for0(i,N-1)
NS[i]=mp(S[i],i);
for0(i,l)
{
pair<int,int> t=NS[Y[i]];
NS[Y[i]]=NS[X[i]];
NS[X[i]]=t;
}
for0(i,N-1)
pos[NS[i].first]=i;
vector<pair<int,int> > ans;
for0(i,N-1)
{
if(NS[i].first!=i)
{
int t=pos[i];
ans.push_back({NS[i].first,NS[t].first});
pos[NS[i].first]=t;
pos[i]=i;
pair<int,int> c=NS[t];
NS[t]=NS[i];
NS[i]=c;
}
}
int H[200002];
pos[200002];
for0(i,N-1)
H[i]=S[i];
for0(i,N-1)
pos[H[i]]=i;
for0(i,l)
{
pos[H[X[i]]]=Y[i];
pos[H[Y[i]]]=X[i];
int t=H[Y[i]];
H[Y[i]]=H[X[i]];
H[X[i]]=t;
P[i]=pos[ans[i].first];
Q[i]=pos[ans[i].second];
pos[H[P[i]]]=Q[i];
pos[H[Q[i]]]=P[i];
t=H[Q[i]];
H[Q[i]]=H[P[i]];
H[P[i]]=t;
}
return (l+1);
}
int m=(l+r)/2;
int NS[200002];
int pos[200002];
for0(i,N-1)
NS[i]=S[i];
for0(i,m)
{
int p=NS[Y[i]];
NS[Y[i]]=NS[X[i]];
NS[X[i]]=p;
}
for0(i,N-1)
pos[NS[i]]=i;
int q=0;
for0(i,N-1)
{
if(NS[i]!=i)
{
q++;
pos[NS[i]]=pos[i];
NS[pos[i]]=NS[i];
NS[i]=i;
pos[i]=i;
}
}
if(q>(m+1))
l=(m+1);
else
r=m;
}
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:45:31: warning: declaration of 't' shadows a global declaration [-Wshadow]
pair<int,int> t=NS[Y[i]];
^
sorting.cpp:24:5: note: shadowed declaration is here
int t[200002];
^
sorting.cpp:56:25: warning: declaration of 't' shadows a global declaration [-Wshadow]
int t=pos[i];
^
sorting.cpp:24:5: note: shadowed declaration is here
int t[200002];
^
sorting.cpp:66:23: warning: statement has no effect [-Wunused-value]
pos[200002];
~~~~~~~~~~^
sorting.cpp:75:21: warning: declaration of 't' shadows a global declaration [-Wshadow]
int t=H[Y[i]];
^
sorting.cpp:24:5: note: shadowed declaration is here
int t[200002];
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
432 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1892 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 |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
432 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1892 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 |
1920 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
4 ms |
1920 KB |
Output is correct |
11 |
Correct |
4 ms |
1920 KB |
Output is correct |
12 |
Correct |
4 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
3 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
432 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
3 ms |
1920 KB |
Output is correct |
4 |
Correct |
4 ms |
1892 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 |
1920 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
256 KB |
Output is correct |
10 |
Correct |
4 ms |
1920 KB |
Output is correct |
11 |
Correct |
4 ms |
1920 KB |
Output is correct |
12 |
Correct |
4 ms |
1920 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
3 ms |
1920 KB |
Output is correct |
15 |
Correct |
3 ms |
1920 KB |
Output is correct |
16 |
Correct |
5 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 |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
2048 KB |
Output is correct |
22 |
Correct |
4 ms |
2020 KB |
Output is correct |
23 |
Correct |
6 ms |
2048 KB |
Output is correct |
24 |
Correct |
4 ms |
2048 KB |
Output is correct |
25 |
Correct |
4 ms |
2048 KB |
Output is correct |
26 |
Correct |
4 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 |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
2048 KB |
Output is correct |
6 |
Correct |
4 ms |
2048 KB |
Output is correct |
7 |
Correct |
4 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 |
5 ms |
2048 KB |
Output is correct |
11 |
Correct |
5 ms |
2048 KB |
Output is correct |
12 |
Correct |
4 ms |
2048 KB |
Output is correct |
13 |
Correct |
5 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 |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
2048 KB |
Output is correct |
6 |
Correct |
4 ms |
2048 KB |
Output is correct |
7 |
Correct |
4 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 |
5 ms |
2048 KB |
Output is correct |
11 |
Correct |
5 ms |
2048 KB |
Output is correct |
12 |
Correct |
4 ms |
2048 KB |
Output is correct |
13 |
Correct |
5 ms |
2048 KB |
Output is correct |
14 |
Correct |
4 ms |
2048 KB |
Output is correct |
15 |
Correct |
233 ms |
11868 KB |
Output is correct |
16 |
Correct |
220 ms |
12164 KB |
Output is correct |
17 |
Correct |
246 ms |
12688 KB |
Output is correct |
18 |
Correct |
35 ms |
5368 KB |
Output is correct |
19 |
Correct |
182 ms |
10828 KB |
Output is correct |
20 |
Correct |
176 ms |
11292 KB |
Output is correct |
21 |
Correct |
219 ms |
11204 KB |
Output is correct |
22 |
Correct |
252 ms |
12844 KB |
Output is correct |
23 |
Correct |
275 ms |
13308 KB |
Output is correct |
24 |
Correct |
311 ms |
12908 KB |
Output is correct |
25 |
Correct |
308 ms |
12804 KB |
Output is correct |
26 |
Correct |
223 ms |
11140 KB |
Output is correct |
27 |
Correct |
201 ms |
10708 KB |
Output is correct |
28 |
Correct |
271 ms |
12752 KB |
Output is correct |
29 |
Correct |
239 ms |
12240 KB |
Output is correct |
30 |
Correct |
136 ms |
9972 KB |
Output is correct |
31 |
Correct |
251 ms |
12572 KB |
Output is correct |
32 |
Correct |
246 ms |
12684 KB |
Output is correct |
33 |
Correct |
262 ms |
12992 KB |
Output is correct |
34 |
Correct |
224 ms |
12864 KB |
Output is correct |
35 |
Correct |
197 ms |
10880 KB |
Output is correct |
36 |
Correct |
53 ms |
8952 KB |
Output is correct |
37 |
Correct |
307 ms |
13252 KB |
Output is correct |
38 |
Correct |
278 ms |
12684 KB |
Output is correct |
39 |
Correct |
293 ms |
12920 KB |
Output is correct |