답안 #1098442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098442	2024-10-09T11:46:27 Z	alexander707070	정렬하기 (IOI15_sorting)	C++14	74 / 100	1000 ms	15816 KB

sorting

#include<bits/stdc++.h>
#include "sorting.h"

#define MAXN 200007
using namespace std;

int n,m,q,br;
int pos[MAXN],s[MAXN],post[MAXN];

int to[MAXN];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N; m=M;

	for(int stop=0;stop<=n;stop++){

		for(int i=0;i<n;i++)s[i]=i;
		for(int i=0;i<stop;i++)swap(s[X[i]],s[Y[i]]);

		for(int i=0;i<n;i++)to[s[i]]=i;
		for(int i=0;i<n;i++){
			s[i]=S[i]; pos[s[i]]=i;
			post[to[i]]=i;
		}

		int pt=0;
		for(int i=0;i<stop;i++){
			P[i]=Q[i]=0;

			swap(s[X[i]],s[Y[i]]);
			swap(to[X[i]],to[Y[i]]);

			swap(pos[s[X[i]]],pos[s[Y[i]]]);
			swap(post[to[X[i]]],post[to[Y[i]]]);

			while(pt<n and to[pos[pt]]==pt)pt++;
			if(pt==n)continue;

			P[i]=pos[pt]; Q[i]=post[pt];

			swap(s[P[i]],s[Q[i]]);
			swap(pos[s[P[i]]],pos[s[Q[i]]]);
		}

		q=stop; br=0;
		for(int i=0;i<n;i++){
			s[i]=S[i];
			if(s[i]==i)br++;
		}

		for(int i=0;i<stop;i++){
			if(br==n)return i;

			if(s[X[i]]==X[i])br--;
			if(s[Y[i]]==Y[i])br--;

			swap(s[X[i]],s[Y[i]]);

			if(s[X[i]]==X[i])br++;
			if(s[Y[i]]==Y[i])br++;

			if(s[P[i]]==P[i])br--;
			if(s[Q[i]]==Q[i])br--;
			
			swap(s[P[i]],s[Q[i]]);

			if(s[P[i]]==P[i])br++;
			if(s[Q[i]]==Q[i])br++;
		}

		if(br==n)return q;
	}
}

Compilation message

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

Subtask #1

8.0 / 8.0

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

Subtask #2

12.0 / 12.0

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

Subtask #3

16.0 / 16.0

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

Subtask #4

18.0 / 18.0

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

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	348 KB	Output is correct
2	Correct	36 ms	856 KB	Output is correct
3	Correct	33 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	2 ms	452 KB	Output is correct
6	Correct	4 ms	860 KB	Output is correct
7	Correct	18 ms	624 KB	Output is correct
8	Correct	34 ms	604 KB	Output is correct
9	Correct	36 ms	600 KB	Output is correct
10	Correct	45 ms	600 KB	Output is correct
11	Correct	33 ms	604 KB	Output is correct
12	Correct	18 ms	600 KB	Output is correct
13	Correct	49 ms	604 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct

Subtask #6

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	348 KB	Output is correct
2	Correct	36 ms	856 KB	Output is correct
3	Correct	33 ms	600 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	2 ms	452 KB	Output is correct
6	Correct	4 ms	860 KB	Output is correct
7	Correct	18 ms	624 KB	Output is correct
8	Correct	34 ms	604 KB	Output is correct
9	Correct	36 ms	600 KB	Output is correct
10	Correct	45 ms	600 KB	Output is correct
11	Correct	33 ms	604 KB	Output is correct
12	Correct	18 ms	600 KB	Output is correct
13	Correct	49 ms	604 KB	Output is correct
14	Correct	1 ms	600 KB	Output is correct
15	Execution timed out	1070 ms	15816 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-