oj.uz

Submission #789866

# Submission time Handle Problem Language Result Execution time Memory
789866 2023-07-22T06:34:28 Z peteza Sorting (IOI15_sorting) C++14
74 / 100
 1000 ms 17800 KB 
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;

int cur[200005], N;
bool vis[200005];
int pos[200005];

int countcompo() {
	for(int j=0;j<=N;j++) vis[j] = 0;
	int cnt = 0;
	for(int i=0;i<N;i++) {
		if(vis[i]) continue;
		vis[i] = 1;
		cnt++;
		int j=i;
		do vis[j=cur[j]] = 1; while(j != i);
	}
	return cnt;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ::N = N;
	for(int i=0;i<N;i++) cur[i] = S[i];
	memset(P, 0, 4*M); memset(Q, 0, 4 * M);
	if(countcompo() == N) return 0;
	for(int i=0;i<M;i++) {
		swap(cur[X[i]], cur[Y[i]]);
		int cnt = N-countcompo();
		if(cnt <= i+1) { //check if after swapping i, minimum is less than that of i+1
			//if so then return 
			memset(vis, 0, sizeof vis);
			vector<pair<int, int>> ans;
			for(int i=0;i<N;i++) {
				if(!vis[i]) {
					vis[i] = 1;
					int l = i, j = cur[i];
					while(j != i) {
						vis[j] = 1;
						ans.emplace_back(l, j); l = j;
						j = cur[j];
					}
				}
			}
			//cout << ans.size() << ": \n";
			//for(auto e:ans) cout << e.first << ' ' << e.second << '\n';
			int k = 0;
			for(int i=0;i<N;i++) pos[S[i]] = i;
			for(int j=0;j<=i;j++) {
				swap(pos[S[X[j]]], pos[S[Y[j]]]);
				swap(S[X[j]], S[Y[j]]);
				if(!ans.empty()) {
					P[k] = pos[ans.back().first];
					Q[k++] = pos[ans.back().second];
					ans.pop_back();
				}
			}
			return i+1;
		}
	}
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:22:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   22 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:5:18: note: shadowed declaration is here
    5 | int cur[200005], N;
      |                  ^
sorting.cpp:34:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   34 |    for(int i=0;i<N;i++) {
      |            ^
sorting.cpp:27:10: note: shadowed declaration is here
   27 |  for(int i=0;i<M;i++) {
      |          ^
sorting.cpp:48:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   48 |    for(int i=0;i<N;i++) pos[S[i]] = i;
      |            ^
sorting.cpp:27:10: note: shadowed declaration is here
   27 |  for(int i=0;i<M;i++) {
      |          ^
sorting.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 436 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 576 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 576 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 448 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 2 ms 724 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 11 ms 620 KB Output is correct
3 Correct 9 ms 608 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 11 ms 724 KB Output is correct
9 Correct 9 ms 604 KB Output is correct
10 Correct 11 ms 708 KB Output is correct
11 Correct 9 ms 624 KB Output is correct
12 Correct 5 ms 616 KB Output is correct
13 Correct 9 ms 724 KB Output is correct
14 Correct 1 ms 580 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 11 ms 620 KB Output is correct
3 Correct 9 ms 608 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 11 ms 724 KB Output is correct
9 Correct 9 ms 604 KB Output is correct
10 Correct 11 ms 708 KB Output is correct
11 Correct 9 ms 624 KB Output is correct
12 Correct 5 ms 616 KB Output is correct
13 Correct 9 ms 724 KB Output is correct
14 Correct 1 ms 580 KB Output is correct
15 Execution timed out 1054 ms 17800 KB Time limit exceeded
16 Halted 0 ms 0 KB -