Submission #797242

#	Time	Username	Problem	Language	Result	Execution time	Memory
797242		Ronin13	Sorting (IOI15_sorting)	C++17	100 / 100	140 ms	21764 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) {
    int l = -1, r = m;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		int b[n];
		for(int i = 0; i < n; i++){
			b[i] = s[i];
		}
		for(int i = 0; i < mid; i++){
			swap(b[x[i]], b[y[i]]);
		}
		int pos[n];
		int p[n];
		for(int i = 0; i < n; i++){
			pos[s[i]] = i;
			p[b[i]] = i;
		}
		int a[n];
		for(int i = 0; i < n; i++){
			a[i] = s[i];;
		}
		int ind = 0;
		for(int i = 0; i < mid; i++){
			swap(pos[a[x[i]]], pos[a[y[i]]]);
			swap(a[x[i]], a[y[i]]);
			while(ind < n && b[ind] == ind) ind++;
			if(ind == n) continue;
			int x = b[ind];
			swap(b[ind], b[p[ind]]);
			swap(p[x], p[ind]);
			
			swap(pos[x], pos[ind]);
			swap(a[pos[x]], a[pos[ind]]);
		}
		bool good = true;
		for(int i = 0; i < n; i++){
			if(a[i] != i) good = false;
		}
		good ? r = mid : l = mid;
	}
	int b[n];
	for(int i = 0; i < n; i++){
		b[i] = s[i];
	}
	int p[n];
	for(int i = 0; i < r; i++){
		swap(b[x[i]], b[y[i]]);
	}
	int pos[n];
	for(int i = 0; i < n; i++){
		pos[s[i]] = i;
		p[b[i]] = i;
	}
	int a[n];
	for(int i = 0; i < n; i++){
		a[i] = s[i];;
	}
	int ind = 0;
	for(int i = 0; i < r; i++){
		swap(pos[a[x[i]]], pos[a[y[i]]]);
		swap(a[x[i]], a[y[i]]);
		while(ind < n && b[ind] == ind) ind++;
		if(ind == n) {
			P[i] = Q[i] = 0;
			continue;
		}
		int x = b[ind];
		swap(b[ind], b[p[ind]]);
		swap(p[x], p[ind]);
		P[i] = pos[x], Q[i] = pos[ind];
		swap(pos[x], pos[ind]);
		swap(a[pos[x]], a[pos[ind]]);
	}
	bool good = true;
	for(int i = 0; i < n; i++){
		if(a[i] != i) good = false;
	}
	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:39:8: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   39 |    int x = b[ind];
      |        ^
sorting.cpp:12:46: note: shadowed declaration is here
   12 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) {
      |                                          ~~~~^~~
sorting.cpp:78:7: warning: declaration of 'int x' shadows a parameter [-Wshadow]
   78 |   int x = b[ind];
      |       ^
sorting.cpp:12:46: note: shadowed declaration is here
   12 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) {
      |                                          ~~~~^~~
sorting.cpp:85:7: warning: variable 'good' set but not used [-Wunused-but-set-variable]
   85 |  bool good = true;
      |       ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26