oj.uz

Submission #973995

# Submission time Handle Problem Language Result Execution time Memory
973995 2024-05-02T14:30:13 Z PagodePaiva Sorting (IOI15_sorting) C++17
20 / 100
 7 ms 620 KB 
#include<bits/stdc++.h>
#include "sorting.h"

using namespace std;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int pai[n];
    for(int i = 0;i < n;i++){
    	pai[s[i]] = i;
    }
    bool aux = true;
    for(int i = 1;i < n;i++){
    	if(s[i] < s[i-1]) aux = false;
    }
    if(aux){
    	return 0;
    }
    int l = 0, r = m-1;
    int resp = -1;
    while(l <= r){
    	int mid = (l+r)>>1;
    	int paimid[n];
    	int mark[n];
    	for(int i = 0;i < n;i++) {
    		paimid[i] = pai[i];
    		mark[i] = false;
    	}
    	for(int i = l;i <= mid;i++){
    		swap(paimid[x[i]], paimid[y[i]]);
    	}
    	int res = 0;
    	for(int i = 0;i < n;i++){
    		if(mark[i]) continue;
    		int x = i;
    		while(!mark[x]){
    			res++;
    			mark[x] = true;
    			x = paimid[x];
    		}
    		res--;
    	}
    	if(res <= mid+1){
    		r = mid-1;
    		resp = mid;
    	}
    	else{
    		for(int i = 0;i < n;i++) pai[i] = paimid[i];
    		l = mid+1;
    	}
    }
    // cout << resp << '\n';
    for(int i = 0;i < m;i++) p[i] = q[i] = 0;
	vector <int> v;
	for(int i = 0;i < n;i++){
		v.push_back(i);
	}
	for(int i = resp;i >= 0;i--){
		swap(v[x[i]], v[y[i]]);
	}
	int at = 0;
	for(int i = 0;i <= resp;i++){
		bool aux = true;
		for(int j = 1;j < n;j++){
			if(s[j] < s[j-1]) aux = false;
		}
		if(aux) break;
		swap(v[x[i]], v[y[i]]);
		swap(s[x[i]], s[y[i]]);
		int poss, posv;
		while(true){
			if(at == n){
				p[i] = 0;
				q[i] = 0;
				return i+1;
			}
			for(int j = 0;j < n;j++){
				if(s[j] == at) poss = j;
				if(v[j] == at) posv = j;
			}
			if(poss == posv){
				at++;
				continue;
			}
			// cout << poss << ' ' << posv << '\n';
			p[i] = poss;
			q[i] = posv;
			at++;
			break;
		}
		swap(s[poss], s[posv]);
		if(at == n){
		// for(int j = 0;j <= i;j++) cout << p[j] << ' ' << q[j] << "\n";
			return i+1;
		}
		while(true){
			if(at == n){
				// for(int j = 0;j <= i;j++) cout << p[j] << ' ' << q[j] << "\n";
				return i+1;
			}
			int poss, posv;
			for(int j = 0;j < n;j++){
				if(s[j] == at) poss = j;
				if(v[j] == at) posv = j;
			}
			if(poss == posv){
				at++;
				continue;
			}
			break;
		}
	}
	// for(int j = 0;j <= resp;j++) cout << p[j] << ' ' << q[j] << "\n";
	return resp+1;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:34:11: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   34 |       int x = i;
      |           ^
sorting.cpp:6:46: note: shadowed declaration is here
    6 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
      |                                          ~~~~^~~
sorting.cpp:62:8: warning: declaration of 'aux' shadows a previous local [-Wshadow]
   62 |   bool aux = true;
      |        ^~~
sorting.cpp:11:10: note: shadowed declaration is here
   11 |     bool aux = true;
      |          ^~~
sorting.cpp:100:8: warning: declaration of 'poss' shadows a previous local [-Wshadow]
  100 |    int poss, posv;
      |        ^~~~
sorting.cpp:69:7: note: shadowed declaration is here
   69 |   int poss, posv;
      |       ^~~~
sorting.cpp:100:14: warning: declaration of 'posv' shadows a previous local [-Wshadow]
  100 |    int poss, posv;
      |              ^~~~
sorting.cpp:69:13: note: shadowed declaration is here
   69 |   int poss, posv;
      |             ^~~~
sorting.cpp:105:4: warning: 'posv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |    if(poss == posv){
      |    ^~
sorting.cpp:105:4: warning: 'poss' may be used uninitialized in this function [-Wmaybe-uninitialized]
sorting.cpp:90:19: warning: 'posv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   swap(s[poss], s[posv]);
      |                   ^~~~
sorting.cpp:90:10: warning: 'poss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |   swap(s[poss], s[posv]);
      |          ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 620 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 620 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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