Submission #1030332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030332		pcc	정렬하기 (IOI15_sorting)	C++17	0 / 100	1 ms	604 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(){
	return done == N;
}

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;
}

void OP(int id){
	auto [a,b] = arr[id];
	act(a,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]);

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

	/*
	for(int i = 0;i+2<N;i++){
		OP(i);
		if(check())return i;
		P[i] = pos[i+2],Q[i] = i+2;
		act(i+2,pos[i+2]);
		assert(perm[i+2] == i+2);
		if(check())return i;
	}
	OP(N-2);
	P[N-2] = Q[N-2] = 0;
	if(check())return N-1;
	else{
		P[N-2] = 0;
		Q[N-2] = 1;
		return N-1;
	}
	*/
	return -1;
}

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