Submission #1011668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011668		hotboy2703	Sorting (IOI15_sorting)	C++17	100 / 100	148 ms	23172 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2e5+100;
ll p[MAXN];
ll pos[MAXN];
void sw(ll x,ll y){
    swap(p[x],p[y]);
    swap(pos[p[x]],pos[p[y]]);
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
    ll l = 0;
    ll r = n - 1;
    vector <pll> ans;
    while (l <= r){
        ll mid = (l + r) >> 1;
        for (ll i = 0;i < n;i ++){
            p[i] = S[i];
            pos[p[i]] = i;
        }
        for (ll i = 0;i < mid;i ++){
            sw(X[i],Y[i]);
        }
        vector <pll> val;
        for (ll i = 0;i < n;i ++){
            if (p[i] != i){
                val.push_back(MP(i,p[i]));
                sw(i,pos[i]);
            }
        }
        if (sz(val) > mid){
            l = mid + 1;
        }
        else {
            while (sz(val) < mid)val.push_back(MP(0,0));
            for (ll i = mid - 1;i >= 0;i --){
                sw(pos[val[i].fi],pos[val[i].se]);
                val[i] = MP(pos[val[i].fi],pos[val[i].se]);
                sw(X[i],Y[i]);
            }
            ans = val;
            r = mid - 1;
        }
    }
    for (ll i =0 ;i < sz(ans);i ++){
        tie(P[i],Q[i]) = ans[i];
    }
	return sz(ans);
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:19:39: warning: unused parameter 'm' [-Wunused-parameter]
   19 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

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