제출 #1357082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357082		enzy	정렬하기 (IOI15_sorting)	C++20	74 / 100	1093 ms	7960 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int f[maxn], marc[maxn], fim[maxn], a[maxn], b[maxn], cnt;
void dfs(int u){
	marc[u]++;
	if(!marc[f[u]]) dfs(f[u]);
}

void get(int u){
	// cerr << u << ' ';
	fim[u]++;
	if(!fim[f[u]]){
		a[cnt]=u; b[cnt]=f[u];
		cnt++;
		get(f[u]);
	}/*else cerr << '\n';*/
}

int findSwapPairs(int n, int s[], int m, int X[], int Y[], int P[], int Q[]){
	cnt=0;
	auto check=[&](int z[]){
		for(int i=1;i<n;i++) if(z[i-1]>z[i]) return false;
		return true;
	};

	if(check(s)) return 0;

	auto calc=[&](){
		for(int i=0;i<n;i++) marc[i]=0, f[i]=s[i];
		int ret=0;
		for(int i=0;i<n;i++){
			if(!marc[i]){
				ret++;
				dfs(i);
			}
		}
		return ret;
	};

	int og[n], aux[n];
	for(int i=0;i<n;i++) og[s[i]]=i, aux[i]=s[i];

    for(int i=0;i<m;i++){
		swap(s[X[i]],s[Y[i]]);
		int qtd=n-calc();
		if(qtd<=i+1){ // doable
			// cerr << "da pra fzr em: " << i+1 << '\n';
			// cerr << "s: ";
			// for(int j=0;j<n;j++) cerr << s[j] << ' ';
			// cerr << '\n';
			// cerr << "f: ";
			// for(int j=0;j<n;j++) cerr << f[j] << ' ';
			// cerr << '\n';
			for(int j=0;j<n;j++) if(!fim[j]) get(j);
			for(int j=0;j<=i;j++){
				swap(og[aux[X[j]]],og[aux[Y[j]]]);
				swap(aux[X[j]],aux[Y[j]]);
				P[j]=og[a[j]]; Q[j]=og[b[j]];
				swap(og[a[j]],og[b[j]]);
				swap(aux[og[a[j]]],aux[og[b[j]]]);
			}
			// for(int j=0;j<n;j++) cerr << aux[j] << ' ';
			// cerr << '\n';
			assert(check(aux));
			return i+1;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
   70 | }
      | ^

• 서브태스크 1: 8 / 8
• 서브태스크 2: 12 / 12
• 서브태스크 3: 16 / 16
• 서브태스크 4: 18 / 18
• 서브태스크 5: 20 / 20
• 서브태스크 6: 0 / 26