Submission #288369

#	Time	Username	Problem	Language	Result	Execution time	Memory
288369		shayan_p	Sorting (IOI15_sorting)	C++17	100 / 100	370 ms	14232 KiB

sorting

#include<bits/stdc++.h>
#include "sorting.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

const int maxn = 6e5 + 10, mod = 1e9 + 7;

bool mark[maxn];
int _p[maxn];

int findSwapPairs(int n, int p[], int q, int a[], int b[], int A[], int B[]){
    fill(A, A + q, 0);
    fill(B, B + q, 0);
    for(int i = 0; i < n; i++){
	_p[ p[i] ] = i;
    }
    auto Swap = [&](int i, int j){
		    swap(p[i], p[j]);
		    _p[ p[i] ] = i, _p[ p[j] ] = j;
    };
    auto need = [&](){
		    fill(mark, mark + n, 0);
		    int cnt = 0;
		    for(int i = 0; i < n; i++){
			int tmp = i;
			if(!mark[i]){
			    cnt++;
			    while(!mark[tmp]){
				mark[tmp] = 1;
				tmp = p[tmp];
			    }
			}
		    }
		    return n - cnt;
		};
    auto calc_bin = [&](int q){
			for(int i = 0; i < q; i++)
			    Swap(a[i], b[i]);
			int x = need();
			for(int i = q-1; i >= 0; i--)
			    Swap(a[i], b[i]);
			return x <= q;
		    };
    auto solve = [&](int q){
		     fill(mark, mark + n, 0);
		     vector<pii> tdo;
		     for(int i = 0; i < n; i++){
			 int tmp = i;
			 if(!mark[i]){
			     int SZ = sz(tdo);
			     while(!mark[tmp]){
				 if(i != tmp)
				     tdo.PB({i, tmp});
				 mark[tmp] = 1;
				 tmp = p[tmp];
			     }
			     reverse(tdo.begin() + SZ, tdo.end());
			 }
		     }
		     while(sz(tdo)){
			 q--;
			 int x = tdo.back().F, y = tdo.back().S;
			 tdo.pop_back();
			 A[q] = _p[x], B[q] = _p[y];
			 Swap(A[q], B[q]);
			 Swap(a[q], b[q]);
		     }
		 };
    int l = -1, r = q;
    while(r-l > 1){
	int mid = (l+r) >> 1;
	if(calc_bin(mid))
	    r = mid;
	else
	    l = mid;
    }
    for(int i = 0; i < r; i++){
	Swap(a[i], b[i]);
    }
    solve(r);
    return r;
}

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:46:30: warning: declaration of 'int q' shadows a parameter [-Wshadow]
   46 |     auto calc_bin = [&](int q){
      |                              ^
sorting.cpp:21:39: note: shadowed declaration is here
   21 | int findSwapPairs(int n, int p[], int q, int a[], int b[], int A[], int B[]){
      |                                   ~~~~^
sorting.cpp: In lambda function:
sorting.cpp:54:27: warning: declaration of 'int q' shadows a parameter [-Wshadow]
   54 |     auto solve = [&](int q){
      |                           ^
sorting.cpp:21:39: note: shadowed declaration is here
   21 | int findSwapPairs(int n, int p[], int q, int a[], int b[], int A[], int B[]){
      |                                   ~~~~^

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