답안 #71683 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71683	2018-08-25T11:16:12 Z	Navick	정렬하기 (IOI15_sorting)	C++17	100 / 100	452 ms	22544 KB

sorting

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

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

typedef long long ll;

using namespace std;

const int maxN = 2e5 + 10, maxM = 3 * maxN;

int x[maxM], y[maxM];
int n, q[maxN], tmp[maxN], p[maxN];
bool mark[maxN];
vector <int> a1 ,a2;

int check(int m, bool f = 0)
{
	for (int i=0; i<m; i++)
	{
		int a = p[x[i]], b = p[y[i]];
		p[x[i]] = b, p[y[i]] = a;
	}

	memset(mark, 0, sizeof mark);
	int ted = 0;

	vector <pii > swaps;

	for (int i=0; i<n; i++)
	{
		if(mark[i]) continue ;
		ted ++;
		int curr = i;
		vector <int> vc;
		while(!mark[curr])
		{
			mark[curr] = true;
			if(curr != i) vc.pb(curr);
			curr = p[curr];
		}
		reverse(vc.begin(), vc.end());
		for (auto X : vc){ swaps.pb({X, i});} //if(f)cout << X << ',' << i << endl;}
	}
	
	if(ted < n - m) return 0;
	else if(!f) return 1;

	for (int i=0; i<n; i++) p[i] = tmp[i], q[p[i]] = i;
	
	for (int i=0; i<m; i++)
	{
		int a = p[x[i]], b = p[y[i]];
		p[x[i]] = b, p[y[i]] = a;
		q[b] = x[i], q[a] = y[i];

		if(i >= (int)swaps.size()) continue ;

		int v1 = swaps[i].F, v2 = swaps[i].S;

		int xi = q[v1], yi = q[v2];
		a = p[xi], b = p[yi];
		p[xi] = b, p[yi] = a;
		q[b] = xi, q[a] = yi;

		a1.pb(xi); a2.pb(yi);

	}

	while((int)a1.size() < m) a1.pb(0), a2.pb(0);

	return 1;

}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	int lo = -1, hi = M;
	
	for (int i=0; i<M; i++) x[i] = X[i], y[i] = Y[i];
	
	for (int i=0; i<n; i++) tmp[i] = S[i];

	while(hi - lo > 1)
	{
		for (int i=0; i<n; i++) p[i] = S[i];
		int mid = (lo + hi)/2;
		if(check(mid)) hi = mid;
		else lo = mid;
	}
	
	for (int i=0; i<n; i++) p[i] = S[i];
	check(hi, 1);
	for (int i=0; i<hi; i++) P[i] = a1[i], Q[i] = a2[i];
	return hi;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	768 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	3 ms	768 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	3 ms	640 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	3 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	4 ms	768 KB	Output is correct
12	Correct	4 ms	688 KB	Output is correct
13	Correct	3 ms	768 KB	Output is correct
14	Correct	3 ms	640 KB	Output is correct
15	Correct	317 ms	19668 KB	Output is correct
16	Correct	259 ms	20840 KB	Output is correct
17	Correct	307 ms	21660 KB	Output is correct
18	Correct	88 ms	14720 KB	Output is correct
19	Correct	248 ms	17024 KB	Output is correct
20	Correct	294 ms	17600 KB	Output is correct
21	Correct	315 ms	17752 KB	Output is correct
22	Correct	346 ms	21820 KB	Output is correct
23	Correct	298 ms	22268 KB	Output is correct
24	Correct	391 ms	21844 KB	Output is correct
25	Correct	378 ms	21784 KB	Output is correct
26	Correct	330 ms	17336 KB	Output is correct
27	Correct	238 ms	16660 KB	Output is correct
28	Correct	425 ms	21684 KB	Output is correct
29	Correct	452 ms	20340 KB	Output is correct
30	Correct	196 ms	14976 KB	Output is correct
31	Correct	444 ms	20468 KB	Output is correct
32	Correct	350 ms	21888 KB	Output is correct
33	Correct	379 ms	21280 KB	Output is correct
34	Correct	445 ms	20908 KB	Output is correct
35	Correct	330 ms	16936 KB	Output is correct
36	Correct	79 ms	12920 KB	Output is correct
37	Correct	423 ms	22544 KB	Output is correct
38	Correct	350 ms	21772 KB	Output is correct
39	Correct	404 ms	22116 KB	Output is correct

답안 #71683

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0