Submission #1030346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030346		pcc	Sorting (IOI15_sorting)	C++17	16 / 100	2 ms	856 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
pii arr[mxn];
int perm[mxn],pos[mxn];
int N,M;
int done = 0;

void del(int k){
	done -= (perm[k] == k);
	return;
}
void add(int k){
	done += (perm[k] == k);
}

bool check(){
	for(int i = 0;i<N;i++){
		if(perm[i] != i)return false;
	}
	return true;
}

void act(int a,int b){
	if(a == b)return;
	del(a);del(b);
	swap(perm[a],perm[b]);
	pos[perm[a]] = a;
	pos[perm[b]] = b;
	add(a);add(b);
	return;
}

int findSwapPairs(int NN, int S[], int MM, int X[], int Y[], int P[], int Q[]) {
	N = NN;M = MM;
	for(int i = 0;i<N;i++){
		perm[i] = S[i];
		pos[perm[i]] = i;
		add(i);
	}
	for(int i = 0;i<M;i++)arr[i] = pii(X[i],Y[i]);
	if(check())return P[0] = Q[0] = 0;

	for(int i = 0;i+2<N;i++){
		act(arr[i].fs,arr[i].sc);
		P[i] = pos[i+2],Q[i] = i+2;
		if(check())return i+1;
		act(P[i],Q[i]);
		assert(perm[i+2] == i+2);
		if(check())return i+1;
	}
	act(arr[N-2].fs,arr[N-2].sc);
	P[N-2] = Q[N-2] = 0;
	if(check())return N-1;
	else{
		P[N-2] = 0;
		Q[N-2] = 1;
		act(P[N-2],Q[N-2]);
		assert(check());
		return N-1;
	}
	assert(false);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 16 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26