Submission #140637

#	Time	Username	Problem	Language	Result	Execution time	Memory
140637		baluteshih	Sorting (IOI15_sorting)	C++14	100 / 100	652 ms	19832 KiB

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 (stderr)

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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26