oj.uz

Submission #790053

# Submission time Handle Problem Language Result Execution time Memory
790053 2023-07-22T09:53:16 Z peteza Sorting (IOI15_sorting) C++14
36 / 100
 1 ms 852 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;

	int l=0, r=M;
	while(l <= r) {
		int mid = (l+r) >> 1;
		for(int i=0;i<=mid;i++)
			swap(cur[X[i]], cur[Y[i]]);
		if(N-countcompo()<=mid+1) r=mid-1;
		else l=mid+1;
		for(int i=mid;i>=0;i--)
			swap(cur[X[i]], cur[Y[i]]);
	}

	for(int i=l;i<M;i++) {
		for(int j=0;j<=l;j++) 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:46:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   46 |    for(int i=0;i<N;i++) {
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:49:10: warning: declaration of 'l' shadows a previous local [-Wshadow]
   49 |      int l = i, j = cur[i];
      |          ^
sorting.cpp:28:6: note: shadowed declaration is here
   28 |  int l=0, r=M;
      |      ^
sorting.cpp:60:12: warning: declaration of 'i' shadows a previous local [-Wshadow]
   60 |    for(int i=0;i<N;i++) pos[S[i]] = i;
      |            ^
sorting.cpp:39:10: note: shadowed declaration is here
   39 |  for(int i=l;i<M;i++) {
      |          ^
sorting.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
   73 | }
      | ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 468 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 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 468 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 0 ms 212 KB Output is correct
21 Incorrect 1 ms 852 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -