oj.uz

Submission #967595

# Submission time Handle Problem Language Result Execution time Memory
967595 2024-04-22T13:23:26 Z GrindMachine Sorting (IOI15_sorting) C++17
100 / 100
 260 ms 23660 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
 
*/
 
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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 372 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 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 0 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 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 372 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 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 0 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 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 520 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 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 348 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 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 520 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 210 ms 19360 KB Output is correct
16 Correct 226 ms 20132 KB Output is correct
17 Correct 243 ms 21124 KB Output is correct
18 Correct 35 ms 13400 KB Output is correct
19 Correct 201 ms 20444 KB Output is correct
20 Correct 212 ms 21068 KB Output is correct
21 Correct 213 ms 21288 KB Output is correct
22 Correct 220 ms 16280 KB Output is correct
23 Correct 243 ms 21680 KB Output is correct
24 Correct 251 ms 22792 KB Output is correct
25 Correct 259 ms 20996 KB Output is correct
26 Correct 231 ms 19484 KB Output is correct
27 Correct 210 ms 19068 KB Output is correct
28 Correct 256 ms 21280 KB Output is correct
29 Correct 247 ms 22120 KB Output is correct
30 Correct 195 ms 18792 KB Output is correct
31 Correct 250 ms 20752 KB Output is correct
32 Correct 235 ms 20876 KB Output is correct
33 Correct 250 ms 21132 KB Output is correct
34 Correct 250 ms 20840 KB Output is correct
35 Correct 204 ms 22020 KB Output is correct
36 Correct 118 ms 17452 KB Output is correct
37 Correct 256 ms 23660 KB Output is correct
38 Correct 252 ms 22732 KB Output is correct
39 Correct 260 ms 21984 KB Output is correct