답안 #114767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114767	2019-06-02T15:55:21 Z	arman_ferdous	정렬하기 (IOI15_sorting)	C++17	100 / 100	218 ms	28152 KB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 6e5+100;
int n, ss[N], m, x[N], y[N], p[N], q[N];

int tmp[N];
int solve(int M) {
	for(int i = 0; i < n; i++)
		tmp[i] = ss[i];
	for(int i = 0; i < M; i++)
		swap(tmp[x[i]], tmp[y[i]]);

	int cnt = 0;
	for(int i = 0; i < n; ) {
		if(i == tmp[i]) { i++; continue; }
		p[cnt] = tmp[i];
		q[cnt] = tmp[tmp[i]];
		swap(tmp[i], tmp[tmp[i]]);
		cnt++;
	}
	if(cnt > M) return -1;
	while(cnt < M) {
		p[cnt] = 0;
		q[cnt] = 0;
		cnt++;
	}
	return cnt;
}

int pos[N];
int findSwapPairs(int _n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = _n, m = M;
	for(int i = 0; i < n; i++)
		ss[i] = S[i];
	for(int i = 0; i < m; i++)
		x[i] = X[i], y[i] = Y[i];

	int lo = 0, hi = M, idx;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		int R = solve(mid);
		if(R == -1) lo = mid+1;
		else idx = mid, hi = mid-1;
	}
	for(int i = 0; i < n; i++)
		pos[S[i]] = i;
	int R = solve(idx);

	for(int i = 0; i < R; i++) {
		swap(pos[ss[x[i]]], pos[ss[y[i]]]);
		swap(ss[x[i]], ss[y[i]]);

		P[i] = pos[p[i]];
		Q[i] = pos[q[i]];

		swap(pos[p[i]], pos[q[i]]);
		swap(ss[P[i]], ss[Q[i]]);
	}
	return R;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:19: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int R = solve(idx);
                   ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 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	588 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	512 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 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	588 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	157 ms	16376 KB	Output is correct
16	Correct	164 ms	24696 KB	Output is correct
17	Correct	209 ms	26492 KB	Output is correct
18	Correct	64 ms	22264 KB	Output is correct
19	Correct	133 ms	25336 KB	Output is correct
20	Correct	142 ms	26232 KB	Output is correct
21	Correct	136 ms	26256 KB	Output is correct
22	Correct	160 ms	21368 KB	Output is correct
23	Correct	169 ms	26976 KB	Output is correct
24	Correct	199 ms	26744 KB	Output is correct
25	Correct	193 ms	26872 KB	Output is correct
26	Correct	125 ms	26104 KB	Output is correct
27	Correct	113 ms	25208 KB	Output is correct
28	Correct	183 ms	26488 KB	Output is correct
29	Correct	190 ms	26544 KB	Output is correct
30	Correct	84 ms	24796 KB	Output is correct
31	Correct	180 ms	27128 KB	Output is correct
32	Correct	178 ms	26192 KB	Output is correct
33	Correct	216 ms	27128 KB	Output is correct
34	Correct	192 ms	26716 KB	Output is correct
35	Correct	136 ms	25208 KB	Output is correct
36	Correct	55 ms	23804 KB	Output is correct
37	Correct	218 ms	28152 KB	Output is correct
38	Correct	203 ms	26816 KB	Output is correct
39	Correct	206 ms	27388 KB	Output is correct

답안 #114767

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