oj.uz

Submission #1060378

# Submission time Handle Problem Language Result Execution time Memory
1060378 2024-08-15T13:30:09 Z steveonalex Sorting (IOI15_sorting) C++17
36 / 100
 31 ms 59484 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 = 6e5 + 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[]) {
    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, a[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, a[u]}], i-1, {u, a[u]}, 0, m, 1);
        update(mp[{v, a[v]}], i-1, {v, a[v]}, 0, m, 1);
        mp.erase({u, a[u]});
        mp.erase({v, a[v]});
        swap(a[u], a[v]);
        mp[{u, a[u]}] = i;
        mp[{v, a[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;
    }

    vector<int> perm(n);
    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 12 ms 56924 KB Output is correct
2 Correct 13 ms 56924 KB Output is correct
3 Correct 11 ms 56924 KB Output is correct
4 Correct 12 ms 56932 KB Output is correct
5 Correct 17 ms 56820 KB Output is correct
6 Correct 13 ms 56920 KB Output is correct
7 Correct 11 ms 56780 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 56924 KB Output is correct
2 Correct 13 ms 56924 KB Output is correct
3 Correct 11 ms 56924 KB Output is correct
4 Correct 12 ms 56932 KB Output is correct
5 Correct 17 ms 56820 KB Output is correct
6 Correct 13 ms 56920 KB Output is correct
7 Correct 11 ms 56780 KB Output is correct
8 Correct 11 ms 56920 KB Output is correct
9 Correct 16 ms 56924 KB Output is correct
10 Correct 11 ms 56924 KB Output is correct
11 Correct 14 ms 56920 KB Output is correct
12 Correct 13 ms 56920 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56924 KB Output is correct
2 Correct 16 ms 56920 KB Output is correct
3 Correct 13 ms 57064 KB Output is correct
4 Correct 17 ms 56840 KB Output is correct
5 Correct 14 ms 56924 KB Output is correct
6 Correct 11 ms 56920 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 56924 KB Output is correct
2 Correct 13 ms 56924 KB Output is correct
3 Correct 11 ms 56924 KB Output is correct
4 Correct 12 ms 56932 KB Output is correct
5 Correct 17 ms 56820 KB Output is correct
6 Correct 13 ms 56920 KB Output is correct
7 Correct 11 ms 56780 KB Output is correct
8 Correct 11 ms 56920 KB Output is correct
9 Correct 16 ms 56924 KB Output is correct
10 Correct 11 ms 56924 KB Output is correct
11 Correct 14 ms 56920 KB Output is correct
12 Correct 13 ms 56920 KB Output is correct
13 Correct 14 ms 56924 KB Output is correct
14 Correct 16 ms 56920 KB Output is correct
15 Correct 13 ms 57064 KB Output is correct
16 Correct 17 ms 56840 KB Output is correct
17 Correct 14 ms 56924 KB Output is correct
18 Correct 11 ms 56920 KB Output is correct
19 Correct 16 ms 56920 KB Output is correct
20 Correct 11 ms 56944 KB Output is correct
21 Incorrect 31 ms 59484 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 57944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 57944 KB Output isn't correct
2 Halted 0 ms 0 KB -