oj.uz

Submission #967602

# Submission time Handle Problem Language Result Execution time Memory
967602 2024-04-22T13:36:15 Z GrindMachine Sorting (IOI15_sorting) C++17
100 / 100
 292 ms 19404 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 448 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 448 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 608 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 856 KB Output is correct
25 Correct 1 ms 612 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 520 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 520 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 226 ms 15828 KB Output is correct
16 Correct 228 ms 16308 KB Output is correct
17 Correct 252 ms 17272 KB Output is correct
18 Correct 34 ms 9812 KB Output is correct
19 Correct 244 ms 16620 KB Output is correct
20 Correct 219 ms 16844 KB Output is correct
21 Correct 244 ms 17052 KB Output is correct
22 Correct 215 ms 14740 KB Output is correct
23 Correct 253 ms 17376 KB Output is correct
24 Correct 248 ms 19404 KB Output is correct
25 Correct 251 ms 17136 KB Output is correct
26 Correct 254 ms 15456 KB Output is correct
27 Correct 219 ms 16788 KB Output is correct
28 Correct 292 ms 17292 KB Output is correct
29 Correct 243 ms 18028 KB Output is correct
30 Correct 197 ms 14808 KB Output is correct
31 Correct 253 ms 16472 KB Output is correct
32 Correct 240 ms 18548 KB Output is correct
33 Correct 274 ms 17092 KB Output is correct
34 Correct 241 ms 16944 KB Output is correct
35 Correct 217 ms 16408 KB Output is correct
36 Correct 133 ms 13428 KB Output is correct
37 Correct 269 ms 19184 KB Output is correct
38 Correct 247 ms 17360 KB Output is correct
39 Correct 246 ms 17932 KB Output is correct