제출 #967602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
967602		GrindMachine	정렬하기 (IOI15_sorting)	C++17	100 / 100	292 ms	19404 KiB

sorting

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*
 
refs:
edi

if we can check if ans <= mid, then we can run a b.s
how to check if ans <= mid?

key idea:
look at both players' swaps separately
bob swaps plates, alice swaps apples
goal: apple i belongs to plate i

plates initially 0,1,...,n-1
apples initially a[0],a[1],...,a[n-1]

because both guys operate individually, one can do all ops before the other (inter order doesnt matter)

apples = 4 3 2 1 0
plates = 0 1 2 3 4 

plates (0,1):
apples = 4 3 2 1 0
plates = 1 0 2 3 4 

plates (1,2):
apples = 4 3 2 1 0
plates = 2 0 1 3 4 

plates (2,3):
apples = 4 3 2 1 0
plates = 3 0 1 2 4 

now consider alice's swaps
alice only swaps apples
the final arrangement of plates is already decided
apple i needs to go on plate i
create a functional graph from each apple to its respective final position

in the eg above, 4 --> 0 --> 3 (apple 4 needs to go to apple 0's position etc) and 1 --> 2
ans <= mid if sz(to_swap) <= mid (sz(to_swap) = 3), which is true in this case
after each swap of bob, alice swaps one pair of apples

apples (0,3):
apples = 4 0 2 1 3
plates = 3 0 1 2 4

apples (3,4):
apples = 3 0 2 1 4
plates = 3 0 1 2 4

apples (1,2):
apples = 3 0 1 2 4
plates = 3 0 1 2 4

need some care when writing to arrays P[] and Q[]
because we need to fill indices (i.e plates), not apples
can be done on the go by maintaining the order of plates, positions of plates, order of apples and positions of apples on the go

*/
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
#include "sorting.h"
 
int findSwapPairs(int n, int a[], int m, int X[], int Y[], int P[], int Q[]) {
    if(is_sorted(a,a+n)) return 0;

    auto ok = [&](int mid, int t){
        vector<int> plates(n), plate_pos(n);
        iota(all(plates),0), iota(all(plate_pos),0);
        rep(i,mid){
            // swap plates x and y
            int x = X[i], y = Y[i];
            int &p = plate_pos[x], &q = plate_pos[y];
            swap(plates[p],plates[q]);
            swap(p,q);
        }
     
        vector<bool> vis(n);
        vector<pii> to_swap; // pairs of apples that need to be swapped
     
        rep(i,n){
            if(vis[i]) conts;
            int j = i;
            vector<int> apples;
     
            while(!vis[j]){
                vis[j] = 1;
                apples.pb(a[j]);
                j = plate_pos[a[j]];
            }
     
            rep(k,sz(apples)-1){
                to_swap.pb({apples[k],apples.back()});
            }
        }
        
        if(!t){
            return sz(to_swap) <= mid;
        }

        iota(all(plates),0), iota(all(plate_pos),0);
        vector<int> apples(n), apple_pos(n);
        rep(i,n) apples[i] = a[i], apple_pos[a[i]] = i;
        
        rep(i,mid){
            {
                int x = X[i], y = Y[i];
                int &p = plate_pos[x], &q = plate_pos[y];
                swap(plates[p],plates[q]);
                swap(p,q);
            }
     
            if(!to_swap.empty()){
                auto [x,y] = to_swap.back();
                to_swap.pop_back();
                int &p = apple_pos[x], &q = apple_pos[y];
                P[i] = plates[p], Q[i] = plates[q];
                swap(apples[p],apples[q]);
                swap(p,q);
            }
        }
        
        rep(i,n) assert(plates[i] == apples[i]);
        return true;
    };

    int l = 1, r = m;
    int ans = -1;

    while(l <= r){
        int mid = (l+r) >> 1;
        if(ok(mid,0)){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    ok(ans,1);
    return ans;
}

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