oj.uz

Submission #790185

# Submission time Handle Problem Language Result Execution time Memory
790185 2023-07-22T11:52:40 Z PoonYaPat Sorting (IOI15_sorting) C++14
100 / 100
 773 ms 69124 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,m,b[200005],x[200005],y[200005],p[200005],cnt;
vector<pii> ans,v;
vector<int> adj[200005],group[200005],temp;
int a[200005],pos[200005],val[200005],c[200005];
bool vis[200005];

void dfs(int x, int st) {
	temp.push_back(x);
	vis[x]=true;
	for (auto s : adj[x]) {
		if (s==st) for (auto s : temp) group[cnt].push_back(s);
		else dfs(s,st);
	}
	temp.pop_back();
}


bool check(int h, bool mode) {
	v.clear();
	cnt=0;
	memset(vis,0,sizeof(vis));
	for (int i=0; i<n; ++i) a[i]=i, val[i]=i, c[i]=b[i], p[i]=i, adj[i].clear(), group[i].clear();
	for (int i=h; i>=0; --i) swap(a[x[i]],a[y[i]]);

	for (int i=0; i<n; ++i) pos[a[i]]=i;
	for (int i=0; i<n; ++i) adj[i].push_back(pos[c[i]]);

	for (int i=0; i<n; ++i) {
		if (!vis[i]) {
			dfs(i,i);
			for (int j=0; j<group[cnt].size()-1; ++j) v.push_back(pii(group[cnt][j],group[cnt][j+1]));
			++cnt;
		}
	}

	if (mode) {
		int cnt=0;
		for (int i=0; i<=h; ++i) {
			swap(val[p[x[i]]],val[p[y[i]]]);
			swap(p[x[i]],p[y[i]]);

			if (v.size()) {
				ans.push_back(pii(val[v.back().first],val[v.back().second]));
				v.pop_back();
			} else ans.push_back(pii(0,0));
		}
	}

	if (v.size()<=h+1) return true;
	else return false;
}

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) b[i]=S[i], x[i]=X[i], y[i]=Y[i];

	bool ah=true;
	for (int i=0; i<n; ++i) if (b[i]!=i) ah=false;
	if (ah) return 0;

	int l=0, r=m-1;
	while (l<r) {
		int mid=(l+r)/2;
		if (check(mid,0)) r=mid;
		else l=mid+1;
	}
	check(l,1);

	for (int i=0; i<ans.size(); ++i) P[i]=ans[i].first, Q[i]=ans[i].second;
	return ans.size();
}

Compilation message

sorting.cpp: In function 'void dfs(int, int)':
sorting.cpp:12:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   12 | void dfs(int x, int st) {
      |          ~~~~^
sorting.cpp:6:19: note: shadowed declaration is here
    6 | int n,m,b[200005],x[200005],y[200005],p[200005],cnt;
      |                   ^
sorting.cpp:16:24: warning: declaration of 's' shadows a previous local [-Wshadow]
   16 |   if (s==st) for (auto s : temp) group[cnt].push_back(s);
      |                        ^
sorting.cpp:15:12: note: shadowed declaration is here
   15 |  for (auto s : adj[x]) {
      |            ^
sorting.cpp: In function 'bool check(int, bool)':
sorting.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for (int j=0; j<group[cnt].size()-1; ++j) v.push_back(pii(group[cnt][j],group[cnt][j+1]));
      |                  ~^~~~~~~~~~~~~~~~~~~~
sorting.cpp:42:7: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
   42 |   int cnt=0;
      |       ^~~
sorting.cpp:6:49: note: shadowed declaration is here
    6 | int n,m,b[200005],x[200005],y[200005],p[200005],cnt;
      |                                                 ^~~
sorting.cpp:42:7: warning: unused variable 'cnt' [-Wunused-variable]
   42 |   int cnt=0;
      |       ^~~
sorting.cpp:54:14: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  if (v.size()<=h+1) return true;
      |      ~~~~~~~~^~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:74:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i=0; i<ans.size(); ++i) P[i]=ans[i].first, Q[i]=ans[i].second;
      |                ~^~~~~~~~~~~
sorting.cpp:75:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  return ans.size();
      |         ~~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 4 ms 9812 KB Output is correct
6 Correct 4 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 4 ms 9812 KB Output is correct
6 Correct 4 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 4 ms 9916 KB Output is correct
11 Correct 4 ms 9940 KB Output is correct
12 Correct 4 ms 9940 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9940 KB Output is correct
3 Correct 4 ms 9920 KB Output is correct
4 Correct 4 ms 9880 KB Output is correct
5 Correct 4 ms 9940 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9856 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 4 ms 9812 KB Output is correct
6 Correct 4 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 4 ms 9916 KB Output is correct
11 Correct 4 ms 9940 KB Output is correct
12 Correct 4 ms 9940 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9940 KB Output is correct
15 Correct 4 ms 9920 KB Output is correct
16 Correct 4 ms 9880 KB Output is correct
17 Correct 4 ms 9940 KB Output is correct
18 Correct 5 ms 9940 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 6 ms 9688 KB Output is correct
21 Correct 6 ms 10068 KB Output is correct
22 Correct 5 ms 10068 KB Output is correct
23 Correct 7 ms 10068 KB Output is correct
24 Correct 6 ms 10068 KB Output is correct
25 Correct 5 ms 10068 KB Output is correct
26 Correct 5 ms 10068 KB Output is correct
27 Correct 5 ms 10068 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 6 ms 10324 KB Output is correct
3 Correct 6 ms 10324 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 6 ms 10324 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10432 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10324 KB Output is correct
10 Correct 6 ms 10368 KB Output is correct
11 Correct 7 ms 10244 KB Output is correct
12 Correct 6 ms 10372 KB Output is correct
13 Correct 7 ms 10364 KB Output is correct
14 Correct 5 ms 10196 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10324 KB Output is correct
2 Correct 6 ms 10324 KB Output is correct
3 Correct 6 ms 10324 KB Output is correct
4 Correct 4 ms 9812 KB Output is correct
5 Correct 6 ms 10324 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10432 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 6 ms 10324 KB Output is correct
10 Correct 6 ms 10368 KB Output is correct
11 Correct 7 ms 10244 KB Output is correct
12 Correct 6 ms 10372 KB Output is correct
13 Correct 7 ms 10364 KB Output is correct
14 Correct 5 ms 10196 KB Output is correct
15 Correct 649 ms 58804 KB Output is correct
16 Correct 644 ms 62752 KB Output is correct
17 Correct 603 ms 65200 KB Output is correct
18 Correct 42 ms 24912 KB Output is correct
19 Correct 404 ms 62816 KB Output is correct
20 Correct 366 ms 57348 KB Output is correct
21 Correct 372 ms 59632 KB Output is correct
22 Correct 584 ms 55988 KB Output is correct
23 Correct 729 ms 67020 KB Output is correct
24 Correct 671 ms 65492 KB Output is correct
25 Correct 681 ms 63832 KB Output is correct
26 Correct 388 ms 48828 KB Output is correct
27 Correct 308 ms 48092 KB Output is correct
28 Correct 710 ms 62648 KB Output is correct
29 Correct 439 ms 64516 KB Output is correct
30 Correct 224 ms 45256 KB Output is correct
31 Correct 469 ms 63588 KB Output is correct
32 Correct 773 ms 63396 KB Output is correct
33 Correct 591 ms 66052 KB Output is correct
34 Correct 519 ms 59096 KB Output is correct
35 Correct 379 ms 62660 KB Output is correct
36 Correct 123 ms 48512 KB Output is correct
37 Correct 686 ms 69124 KB Output is correct
38 Correct 706 ms 66708 KB Output is correct
39 Correct 599 ms 64916 KB Output is correct