Submission #140637

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140637	2019-08-04T02:32:03 Z	baluteshih	Sorting (IOI15_sorting)	C++14	100 / 100	652 ms	19832 KB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int seq[200005],pl[200005],rseq[200005],rpl[200005];

void swp(int x,int y)
{
	swap(pl[seq[x]],pl[seq[y]]),swap(seq[x],seq[y]);
}

void rswp(int x,int y)
{
	swap(rpl[rseq[x]],rpl[rseq[y]]),swap(rseq[x],rseq[y]);
}

bool check(int N, int S[], int M, int X[], int Y[], int P[], int Q[],int x)
{
	int nw=0;
	for(int i=0;i<N;++i)
		rseq[i]=seq[i]=S[i],rpl[seq[i]]=pl[seq[i]]=i;
	for(int i=0;i<x;++i)
		swp(X[i],Y[i]),P[i]=Q[i]=0;
	for(int i=0;i<N;++i)
    	if(seq[i]!=i)
    		if(nw>=x)
				return 0;
			else
				rswp(X[nw],Y[nw]),P[nw]=rpl[seq[i]],Q[nw]=rpl[i],rswp(P[nw],Q[nw]),++nw,swp(i,pl[i]);
	return 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    int l=0,r=M;
    while(l<r)
    {
    	int mid=l+r>>1;
    	if(check(N,S,M,X,Y,P,Q,mid)) r=mid;
    	else l=mid+1;
	}
	check(N,S,M,X,Y,P,Q,r);
	return r;
}

Compilation message

sorting.cpp: In function 'bool check(int, int*, int, int*, int*, int*, int*, int)':
sorting.cpp:36:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
      if(seq[i]!=i)
        ^
sorting.cpp:28:32: warning: unused parameter 'M' [-Wunused-parameter]
 bool check(int N, int S[], int M, int X[], int Y[], int P[], int Q[],int x)
                                ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int mid=l+r>>1;
              ~^~

Subtask #1
8.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	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #2
12.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	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	400 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	7 ms	376 KB	Output is correct

Subtask #3
16.0 / 16.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	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct

Subtask #4
18.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	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	400 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	7 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	348 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	3 ms	632 KB	Output is correct
22	Correct	3 ms	636 KB	Output is correct
23	Correct	4 ms	732 KB	Output is correct
24	Correct	4 ms	632 KB	Output is correct
25	Correct	3 ms	632 KB	Output is correct
26	Correct	2 ms	632 KB	Output is correct
27	Correct	4 ms	632 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	536 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	3 ms	548 KB	Output is correct
8	Correct	4 ms	508 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	3 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct

Subtask #6
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	536 KB	Output is correct
2	Correct	4 ms	448 KB	Output is correct
3	Correct	4 ms	508 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	504 KB	Output is correct
6	Correct	3 ms	504 KB	Output is correct
7	Correct	3 ms	548 KB	Output is correct
8	Correct	4 ms	508 KB	Output is correct
9	Correct	4 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	3 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	424 ms	18412 KB	Output is correct
16	Correct	495 ms	18552 KB	Output is correct
17	Correct	625 ms	19192 KB	Output is correct
18	Correct	113 ms	16248 KB	Output is correct
19	Correct	317 ms	18168 KB	Output is correct
20	Correct	327 ms	18552 KB	Output is correct
21	Correct	328 ms	18552 KB	Output is correct
22	Correct	432 ms	17144 KB	Output is correct
23	Correct	503 ms	19704 KB	Output is correct
24	Correct	623 ms	19448 KB	Output is correct
25	Correct	652 ms	19448 KB	Output is correct
26	Correct	450 ms	18552 KB	Output is correct
27	Correct	384 ms	18168 KB	Output is correct
28	Correct	601 ms	19320 KB	Output is correct
29	Correct	598 ms	19052 KB	Output is correct
30	Correct	294 ms	17656 KB	Output is correct
31	Correct	610 ms	19320 KB	Output is correct
32	Correct	468 ms	19192 KB	Output is correct
33	Correct	642 ms	19572 KB	Output is correct
34	Correct	566 ms	19448 KB	Output is correct
35	Correct	338 ms	17944 KB	Output is correct
36	Correct	64 ms	17144 KB	Output is correct
37	Correct	517 ms	19832 KB	Output is correct
38	Correct	520 ms	19320 KB	Output is correct
39	Correct	511 ms	19440 KB	Output is correct

Submission #140637

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0