oj.uz

Submission #1060386

# Submission time Handle Problem Language Result Execution time Memory
1060386 2024-08-15T13:35:46 Z steveonalex Sorting (IOI15_sorting) C++17
74 / 100
 1000 ms 122048 KB 
#include <bits/stdc++.h>
#include "sorting.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct DSU{
    int n;
    vector<int> parent, sz;
    vector<pair<int, int>> history;

    DSU(int _n){
        n = _n;
        parent.resize(n); sz.resize(n, 1);
        for(int i = 0; i<n; ++i) parent[i] = i;
    }

    int find_set(int u){return (u == parent[u]) ? u : find_set(parent[u]);}
    bool same_set(int u, int v){return find_set(u) == find_set(v);}

    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) swap(u, v);
            parent[v] = u;
            sz[u] += sz[v];
            history.push_back({u, v});
            return true;
        }
        return false;
    }

    int get_size(int u){return sz[find_set(u)];}

    int get_version(){return history.size();}
    void roll_back(int version){
        while(get_version() > version){
            int u, v;
            tie(u, v) = history.back(); history.pop_back();
            parent[v] = v;
            sz[u] -= sz[v];
        }
    }
};

const int N = 2e5 + 69;
vector<pair<int, int>> st[N * 4];
int cc_cnt[N];

void update(int u, int v, pair<int, int> val, int l, int r, int id){
    if (u <= l && r <= v){
        st[id].push_back(val);
        return;
    }
    int mid = (l + r) >> 1;
    if (u <= mid) update(u, v, val, l, mid, id * 2);
    if (v > mid) update(u, v, val, mid + 1, r, id * 2 + 1);
}

void traverse(int l, int r, int id, DSU &mst){
    int cur = mst.get_version();
    for(pair<int, int> i: st[id]) mst.join_set(i.first, i.second);
    if (l == r){
        cc_cnt[l] = mst.get_version();
        mst.roll_back(cur);
        // cout << "Time: " << l << "\n";
        // for(pair<int, int> i: mst.history) cout << i.first << " " << i.second << "\n";
        return;
    }
    int mid = (l + r) >> 1;
    traverse(l, mid, id * 2, mst);
    traverse(mid + 1, r, id * 2 + 1, mst);
    mst.roll_back(cur);
}

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[]) {
    minimize(m, n);
    vector<int> perm(n);
    for(int i = 0; i < n; ++i) perm[i] = a[i];

    for(int i = 0; i<=m*4+4; ++i) st[i].clear();
    int r = 0;
    map<pair<int, int>, int> mp;
    for(int i = 0; i<n; ++i){
        mp[{i, perm[i]}] = 0;
    }
    for(int i = 1; i<=m; ++i){
        int u = x[i-1], v = y[i-1];
        if (u == v) continue;
        update(mp[{u, perm[u]}], i-1, {u, perm[u]}, 0, m, 1);
        update(mp[{v, perm[v]}], i-1, {v, perm[v]}, 0, m, 1);
        mp.erase({u, perm[u]});
        mp.erase({v, perm[v]});
        swap(perm[u], perm[v]);
        mp[{u, perm[u]}] = i;
        mp[{v, perm[v]}] = i;
    }

    for(auto i: mp){
        update(i.second, m, i.first, 0, m, 1);
    }

    DSU mst(n);
    traverse(0, m, 1, mst);

    for(int i = 0; i<=m; ++i) if (cc_cnt[i] <= i) {
        r = i;
        break;
    }

    for(int i = 0; i < n; ++i) perm[i] = a[i];
    for(int i = 0; i < r; ++i) swap(perm[x[i]], perm[y[i]]);

    vector<bool> visited(n);
    vector<pair<int,int>> swaps;
    for(int i = 0; i<n; ++i) if (!visited[i]) {
        int u = i;
        while(!visited[u]){
            visited[u] = true;
            if (!visited[perm[u]]) swaps.push_back({u, perm[u]});
            u = perm[u];
        }
    }

    reverse(ALL(swaps));
    vector<int> pos(n);
    for(int i = 0; i<n; ++i) perm[i] = a[i];
    for(int i = 0; i<n; ++i) pos[perm[i]] = i;
    for(int i = 0; i < r; ++i){
        int u = x[i], v = y[i];
        swap(perm[u], perm[v]);
        swap(pos[perm[u]], pos[perm[v]]);
        if (swaps.size()){
            u = pos[swaps.back().first], v = pos[swaps.back().second];
            swaps.pop_back();
        }
        else u = v = 0;
        swap(perm[u], perm[v]);
        swap(pos[perm[u]], pos[perm[v]]);

        p[i] = u, q[i] = v;
    }

    return r;
}

// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     clock_t start = clock();

//     int n; cin >> n;
//     int a[n];
//     for(int i = 0; i<n; ++i) cin >> a[i];

//     int m; cin >> m;
//     int x[m], y[m];
//     for(int i = 0; i<m; ++i) cin >> x[i] >> y[i];

//     int p[m], q[m];
//     memset(p, -1, sizeof p); memset(q, -1, sizeof q);

//     int r = findSwapPairs(n, a, m, x, y, p, q);
//     cout << r << "\n";
//     for(int i = 0; i < r; ++i) {
//         swap(a[x[i]], a[y[i]]);
//         swap(a[p[i]], a[q[i]]);
//         cout << p[i] << " " << q[i] << "\n"; 
//     }

//     for(int i = 0; i < n; ++i) cout << a[i] << " "; cout << "\n";

//     cerr << "Time elapsed: " << clock() - start << " ms\n";

//     return 0;
// }

/*
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

*/

Compilation message

sorting.cpp: In member function 'int DSU::get_version()':
sorting.cpp:79:42: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |     int get_version(){return history.size();}
      |                              ~~~~~~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 3 ms 19800 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19648 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19632 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 3 ms 19800 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19648 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19632 KB Output is correct
8 Correct 4 ms 19804 KB Output is correct
9 Correct 3 ms 19800 KB Output is correct
10 Correct 3 ms 19800 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 3 ms 19804 KB Output is correct
3 Correct 3 ms 19800 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19648 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19632 KB Output is correct
8 Correct 4 ms 19804 KB Output is correct
9 Correct 3 ms 19800 KB Output is correct
10 Correct 3 ms 19800 KB Output is correct
11 Correct 4 ms 19804 KB Output is correct
12 Correct 4 ms 19804 KB Output is correct
13 Correct 3 ms 19804 KB Output is correct
14 Correct 3 ms 19804 KB Output is correct
15 Correct 3 ms 19804 KB Output is correct
16 Correct 4 ms 19668 KB Output is correct
17 Correct 3 ms 19804 KB Output is correct
18 Correct 3 ms 19804 KB Output is correct
19 Correct 3 ms 19804 KB Output is correct
20 Correct 4 ms 19804 KB Output is correct
21 Correct 4 ms 20104 KB Output is correct
22 Correct 5 ms 20060 KB Output is correct
23 Correct 4 ms 20112 KB Output is correct
24 Correct 5 ms 20060 KB Output is correct
25 Correct 6 ms 20112 KB Output is correct
26 Correct 4 ms 20060 KB Output is correct
27 Correct 4 ms 20060 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20312 KB Output is correct
2 Correct 5 ms 20060 KB Output is correct
3 Correct 7 ms 20476 KB Output is correct
4 Correct 6 ms 20328 KB Output is correct
5 Correct 7 ms 20312 KB Output is correct
6 Correct 7 ms 20316 KB Output is correct
7 Correct 7 ms 20336 KB Output is correct
8 Correct 8 ms 20316 KB Output is correct
9 Correct 7 ms 20460 KB Output is correct
10 Correct 7 ms 20316 KB Output is correct
11 Correct 8 ms 20380 KB Output is correct
12 Correct 7 ms 20316 KB Output is correct
13 Correct 7 ms 20416 KB Output is correct
14 Correct 5 ms 20060 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20312 KB Output is correct
2 Correct 5 ms 20060 KB Output is correct
3 Correct 7 ms 20476 KB Output is correct
4 Correct 6 ms 20328 KB Output is correct
5 Correct 7 ms 20312 KB Output is correct
6 Correct 7 ms 20316 KB Output is correct
7 Correct 7 ms 20336 KB Output is correct
8 Correct 8 ms 20316 KB Output is correct
9 Correct 7 ms 20460 KB Output is correct
10 Correct 7 ms 20316 KB Output is correct
11 Correct 8 ms 20380 KB Output is correct
12 Correct 7 ms 20316 KB Output is correct
13 Correct 7 ms 20416 KB Output is correct
14 Correct 5 ms 20060 KB Output is correct
15 Correct 309 ms 58320 KB Output is correct
16 Correct 591 ms 91604 KB Output is correct
17 Correct 895 ms 118732 KB Output is correct
18 Correct 809 ms 112200 KB Output is correct
19 Correct 903 ms 119236 KB Output is correct
20 Correct 962 ms 120316 KB Output is correct
21 Correct 936 ms 120504 KB Output is correct
22 Correct 160 ms 55752 KB Output is correct
23 Correct 542 ms 98048 KB Output is correct
24 Correct 985 ms 120804 KB Output is correct
25 Correct 991 ms 121176 KB Output is correct
26 Correct 807 ms 119744 KB Output is correct
27 Correct 796 ms 118976 KB Output is correct
28 Correct 862 ms 115356 KB Output is correct
29 Correct 896 ms 118236 KB Output is correct
30 Correct 737 ms 121544 KB Output is correct
31 Correct 926 ms 120308 KB Output is correct
32 Correct 357 ms 72620 KB Output is correct
33 Execution timed out 1006 ms 122048 KB Time limit exceeded
34 Halted 0 ms 0 KB -