답안 #71569 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71569	2018-08-25T07:22:21 Z	Sa1378	정렬하기 (IOI15_sorting)	C++17	100 / 100	312 ms	14440 KB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)201*1000)

int b[N],pos[N];
bool mark[N];

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[])
{
	bool flg=1;
	for(int i=0;i<n;i++)if(a[i]!=i)flg=0;
	if(flg)return 0;
    int l=0,r=m+1;
	vector <pair<int,int> > res;
	while(l<r-1)
	{
		int mid=(l+r)/2;
		for(int i=0;i<n;i++)b[i]=a[i],mark[i]=0;
		for(int i=0;i<mid;i++)swap(b[x[i]],b[y[i]]);
		vector <pair<int,int> > vec;
		for(int i=0;i<n;i++)
			if(!mark[i])
			{
				mark[i]=1;
				if(b[i]==i)continue;
				int j=b[i];vec.push_back({i,j});
				while(!mark[j])
				{
					mark[j]=1;
					if(!mark[b[j]])vec.push_back({j,b[j]});
					j=b[j];
				}
			}
		if(vec.size()>mid)l=mid;
		else r=mid,res.swap(vec);
	}
	for(int i=0;i<n;i++)pos[a[i]]=i;
	for(int i=0;i<r;i++)
	{
		if(res.size()<=i){p[i]=q[i]=0;continue;}
		swap(pos[a[x[i]]],pos[a[y[i]]]);
		swap(a[x[i]],a[y[i]]);
		p[i]=pos[res[i].first];q[i]=pos[res[i].second];
		swap(pos[res[i].first],pos[res[i].second]);
		swap(a[pos[res[i].first]],a[pos[res[i].second]]);
	}
	return r;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(vec.size()>mid)l=mid;
      ~~~~~~~~~~^~~~
sorting.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(res.size()<=i){p[i]=q[i]=0;continue;}
      ~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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	3 ms	384 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	4 ms	512 KB	Output is correct
8	Correct	3 ms	508 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	210 ms	13000 KB	Output is correct
16	Correct	222 ms	13236 KB	Output is correct
17	Correct	268 ms	13752 KB	Output is correct
18	Correct	39 ms	5496 KB	Output is correct
19	Correct	174 ms	11976 KB	Output is correct
20	Correct	214 ms	12328 KB	Output is correct
21	Correct	199 ms	12340 KB	Output is correct
22	Correct	205 ms	13960 KB	Output is correct
23	Correct	271 ms	14192 KB	Output is correct
24	Correct	303 ms	14080 KB	Output is correct
25	Correct	312 ms	13828 KB	Output is correct
26	Correct	183 ms	11160 KB	Output is correct
27	Correct	157 ms	11480 KB	Output is correct
28	Correct	276 ms	13752 KB	Output is correct
29	Correct	200 ms	13260 KB	Output is correct
30	Correct	112 ms	9588 KB	Output is correct
31	Correct	242 ms	13596 KB	Output is correct
32	Correct	193 ms	13844 KB	Output is correct
33	Correct	221 ms	14120 KB	Output is correct
34	Correct	202 ms	13960 KB	Output is correct
35	Correct	184 ms	11932 KB	Output is correct
36	Correct	50 ms	7544 KB	Output is correct
37	Correct	278 ms	14440 KB	Output is correct
38	Correct	196 ms	13896 KB	Output is correct
39	Correct	209 ms	14008 KB	Output is correct

답안 #71569

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