Submission #1263991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263991		liangjeremy	Sorting (IOI15_sorting)	C++20	0 / 100	3 ms	328 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[]){
	int lst=0; swap(a[x[0]],a[y[0]]); bool one=false; bool zero=false; 
	if(a[0]==0 || a[1]==0)zero=true;
	if(a[0]==1 || a[1]==1)one=true; 
	if(!one && zero){
		int idx=-1;
		for(int i=2; i<n; i++){
			if(a[i]==0)idx=i; 
		}
		if(a[0]==0){
			p[lst]=1; q[lst]=idx; swap(a[1],a[idx]); lst++; 
		}else{
			p[lst]=0; q[lst]=idx; swap(a[0],a[idx]); lst++; 
		}
	}else if(one && !zero){
		int idx=-1;
		for(int i=2; i<n; i++){
			if(a[i]==1)idx=i;
		}
		if(a[0]==1){
			p[lst]=1; q[lst]=idx; swap(a[1],a[idx]); lst++; 
		}else{
			p[lst]=0; q[lst]=idx; swap(a[0],a[idx]); lst++; 
		}
	}else if(!one && !zero){
		int idx0=-1; int idx1=-1;
		for(int i=2; i<n; i++){
			if(a[i]==1)idx1=i; else if(a[i]==0)idx0=i;
		}
		p[lst]=0; q[lst]=idx0; swap(a[0],a[idx0]); lst++; swap(a[x[0]],a[y[0]]); 
		p[lst]=0; q[lst]=idx1; swap(a[0],a[idx1]); lst++; 
	}
	for(int i=2; i<n+10; i++){
		swap(a[p[0]],a[q[0]]); bool ok=true; 
		for(int j=0; j<n; j++){
			ok&=(a[j]==j); 
		}
		if(ok)break;
		if(i<n){
			if(a[i]==i)continue;
			for(int j=i+1; j<n; j++){
				if(a[j]==i){
					p[lst]=i; q[lst]=j; swap(a[i],a[j]); lst++; break; 
				}
			}
		}
	}
	return lst; 
}

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