답안 #401260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401260	2021-05-09T17:37:28 Z	kshitij_sodani	정렬하기 (IOI15_sorting)	C++14	100 / 100	472 ms	31540 KB

sorting

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
 
#include "sorting.h"
//int cur[200001];
int it[200001];
int n;
int xx[3*200001];
int yy[3*200001];
int pp[3*200001];
int qq[3*200001];
int cur[200001];//position in which it  has to end up
int cur2[200001];//position in which number is currently ends in
//int cur3[2000001];//position which indes up in 
int cur4[200001];
int pos[200001];
//int ind5[200001];
//int cur3[200001];
bool check(int mid){
	for(int i=0;i<n;i++){
		cur[i]=it[i];
		pos[it[i]]=i;
	}
/*	for(int i=0;i<n;i++){
		cout<<cur[i]<<"<";
	}
	cout<<endl;*/
	//cout<<mid<<",,"<<endl;
	for(int ii=0;ii<n;ii++){
			cur4[ii]=ii;
			//ind5[ii]=i;
		}
		for(int j=0;j<mid;j++){
 
			swap(cur4[xx[j]],cur4[yy[j]]);
		}
 
		queue<int> ss;
		for(int i=0;i<n;i++){
			ss.push(i);
		}
		for(int j=0;j<n;j++){
			cur2[cur4[j]]=j;
		}
	for(int i=0;i<mid;i++){
		swap(pos[cur[xx[i]]],pos[cur[yy[i]]]);
		swap(cur[xx[i]],cur[yy[i]]);
		/*for(int ii=0;ii<n;ii++){
			cout<<cur[ii]<<"/";
		}*/
		//cout<<endl;
		//cout<<xx[i]<<"<<"<<yy[i]<<endl;
		/*for(int j=0;j<n;j++){
			cout<<cur[j]<<",";
		}
		cout<<endl;
*/		
		/*for(int ii=0;ii<n;ii++){
			cur4[ii]=ii;
		}
		for(int j=i+1;j<mid;j++){
			swap(cur4[xx[j]],cur4[yy[j]]);
		}*/
		pair<int,int> cur3;
		cur3.a=cur2[xx[i]];
		cur3.b=cur2[yy[i]];
		/*for(int j=0;j<n;j++){
			if(cur4[j]==xx[i]){
				cur3.a=j;
			}
			if(cur4[j]==yy[i]){
				cur3.b=j;
			}
 
		}*/
		swap(cur4[cur3.a],cur4[cur3.b]);
		swap(cur2[xx[i]],cur2[yy[i]]);
		/*for(int j=0;j<n;j++){
			cur2[cur4[j]]=j;
		}*/
		/*for(int j=0;j<n;j++){
			cout<<cur2[j]<<":";
		}
		cout<<endl;*/
		int ind=-1;
	/*	for(int j=0;j<n;j++){
			pos[cur[j]]=j;
		}*/
		while(ss.size()){
			int j=ss.front();
			ss.pop();
			if(cur2[pos[j]]!=cur[pos[j]]){
				ind=pos[j];
				break;
			}

		}
	/*	for(int j=0;j<n;j++){
			if(cur2[j]!=cur[j]){
				ind=j;
				break;
			}
		}*/
		//cout<<ind<<":"<<endl;
		if(ind==-1){
			pp[i]=0;
			qq[i]=0;
		}
		else{
			int ind2=-1;
			for(int j=0;j<n;j++){
				if(cur2[j]==cur[ind]){
					ind2=j;
					break;
				}
			}	
			ind2=cur4[cur[ind]];
			//cout<<ind<<",,,"<<ind2<<endl;
			
			swap(cur[ind2],cur[ind]);
			pp[i]=ind;
			qq[i]=ind2;		
			swap(pos[cur[pp[i]]],pos[cur[qq[i]]]);
 
		}
		/*for(int j=0;j<n;j++){
			cout<<cur[j]<<",";
		}
		cout<<endl;
 */
		/*for(int j=0;j<mid;j++){
 
		}*/
 
	}
	for(int i=0;i<n;i++){
		if(cur[i]!=i){
			return false;
		}
	}
/*	for(int i=0;i<n;i++){
		cout<<cur[i]<<"<";
	}
	cout<<endl;*/
	return true;
}
int findSwapPairs(int nn, int aa[], int m, int x[], int y[], int p[], int q[]){
	n=nn;
	for(int i=0;i<n;i++){
		it[i]=aa[i];
		//cout<<it[i]<<",";
	}
	//cout<<endl;
 
	for(int i=0;i<m;i++){
		xx[i]=x[i];
		yy[i]=y[i];
	}
	int low=-1;
	for(int j=19;j>=0;j--){
		if(low+(1<<j)<=m){
			if(check(low+(1<<j))==false){
				low+=(1<<j);
			}
		}
 
	}
	low+=1;
	//cout<<low<<":"<<endl;
	check(low);
	for(int i=0;i<low;i++){
		p[i]=pp[i];
		q[i]=qq[i];
	}
	return low;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct

Subtask #3

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct

Subtask #4

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	588 KB	Output is correct
22	Correct	2 ms	588 KB	Output is correct
23	Correct	2 ms	588 KB	Output is correct
24	Correct	2 ms	588 KB	Output is correct
25	Correct	2 ms	588 KB	Output is correct
26	Correct	2 ms	588 KB	Output is correct
27	Correct	2 ms	588 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	464 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	4 ms	532 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	3 ms	464 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	2 ms	460 KB	Output is correct

Subtask #6

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	464 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	4 ms	532 KB	Output is correct
5	Correct	2 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	3 ms	460 KB	Output is correct
9	Correct	3 ms	460 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	3 ms	464 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	2 ms	460 KB	Output is correct
15	Correct	314 ms	20672 KB	Output is correct
16	Correct	376 ms	28988 KB	Output is correct
17	Correct	456 ms	30472 KB	Output is correct
18	Correct	169 ms	26228 KB	Output is correct
19	Correct	313 ms	28764 KB	Output is correct
20	Correct	336 ms	29540 KB	Output is correct
21	Correct	328 ms	29584 KB	Output is correct
22	Correct	297 ms	25672 KB	Output is correct
23	Correct	329 ms	31332 KB	Output is correct
24	Correct	461 ms	30812 KB	Output is correct
25	Correct	455 ms	30488 KB	Output is correct
26	Correct	320 ms	29484 KB	Output is correct
27	Correct	303 ms	28768 KB	Output is correct
28	Correct	435 ms	30776 KB	Output is correct
29	Correct	423 ms	30300 KB	Output is correct
30	Correct	254 ms	28088 KB	Output is correct
31	Correct	432 ms	30704 KB	Output is correct
32	Correct	354 ms	30364 KB	Output is correct
33	Correct	458 ms	30860 KB	Output is correct
34	Correct	394 ms	30780 KB	Output is correct
35	Correct	335 ms	28520 KB	Output is correct
36	Correct	137 ms	27920 KB	Output is correct
37	Correct	470 ms	31540 KB	Output is correct
38	Correct	472 ms	30536 KB	Output is correct
39	Correct	452 ms	30668 KB	Output is correct