oj.uz

Submission #974071

# Submission time Handle Problem Language Result Execution time Memory
974071 2024-05-02T17:50:46 Z PagodePaiva Sorting (IOI15_sorting) C++17
0 / 100
 1000 ms 78848 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;
	}
	cout << res << '\n';
	for(int at = 0, i = 0;i <= res;i++){
		while(at < n){
			if(st[at] == v[at]) at++;
			else break;
		}
		if(at == n) return res+1;
		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 res+1;
		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 res+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:75:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   75 |   for(int i = 0;i < n;i++){
      |           ^
sorting.cpp:61:18: note: shadowed declaration is here
   61 |  for(int at = 0, i = 0;i <= res;i++){
      |                  ^
sorting.cpp:83:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   83 |   for(int i = 0;i < n;i++){
      |           ^
sorting.cpp:61:18: note: shadowed declaration is here
   61 |  for(int at = 0, i = 0;i <= res;i++){
      |                  ^
sorting.cpp:53:9: warning: unused variable 'inv' [-Wunused-variable]
   53 |     int inv[n+1], invst[n+1];
      |         ^~~

Subtask #1
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 Incorrect 0 ms 348 KB Hacked
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 0 ms 348 KB Hacked
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 2 ms 344 KB Expected EOLN
3 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 Incorrect 0 ms 348 KB Hacked
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 78848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 78848 KB Time limit exceeded
2 Halted 0 ms 0 KB -