oj.uz

Submission #974068

# Submission time Handle Problem Language Result Execution time Memory
974068 2024-05-02T17:45:15 Z PagodePaiva Sorting (IOI15_sorting) C++17
20 / 100
 1 ms 600 KB 
#include<bits/stdc++.h>
#include "sorting.h"

using namespace std;

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

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:33:11: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   33 |       int x = i;
      |           ^
sorting.cpp:6:47: note: shadowed declaration is here
    6 | int findSwapPairs(int n, int st[], int m, int x[], int y[], int p[], int q[]) {
      |                                           ~~~~^~~
sorting.cpp:53:9: warning: unused variable 'inv' [-Wunused-variable]
   53 |     int inv[n+1], invst[n+1];
      |         ^~~

Subtask #1
8.0 / 8.0

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