oj.uz

Submission #833948

# Submission time Handle Problem Language Result Execution time Memory
833948 2023-08-22T09:44:06 Z Tigerpants Sorting (IOI15_sorting) C++17
100 / 100
 323 ms 44212 KB 
#include "sorting.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) a.size()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)

ll n, m;
vll s;
vpll mek;

struct node {
    ll target;
    ll destination;
    ll index;
    node(ll t, ll d, ll i) {
        target = t; destination = d; index = i;
    }
};

bool destination_comp(const node& lhs, const node& rhs) {return lhs.destination < rhs.destination;}

bool solve(ll r, vpll& ans) {
    vector<node> nodes; // nodes[i].index == i
    rep(i, 0, n) nodes.pb(node(0, i, i));
    // reverse ermek moves and modify index
    for (ll i = r - 1; i >= 0; i--) {
        // swap mek[i].first and mek[i].second
        swap(nodes[mek[i].first].destination, nodes[mek[i].second].destination);
    }
    // assign nodes elements
    rep(i, 0, n) nodes[i].target = s[i];

    vll destination_to_index(n);
    rep(i, 0, n) destination_to_index[nodes[i].destination] = i;

    ll d = 0;
    ll w = destination_to_index[d];
    while (nodes[w].target == nodes[w].destination) {
        d++;
        if (d == n) break;
        w = destination_to_index[d];
    }

    rep(i, 0, r) {
        // simulate mek[i] on indices and then check whether nodes[destination_to_index[d]] needs to move anywhere...
        // simulate mek swapping indices mek[i]
        swap(destination_to_index[nodes[mek[i].first].destination], destination_to_index[nodes[mek[i].second].destination]);
        swap(nodes[mek[i].first].index, nodes[mek[i].second].index);
        swap(nodes[mek[i].first], nodes[mek[i].second]);

        if (d == n) {
            ans.pb(mp(0, 0));
        } else {
            w = destination_to_index[d];
            // move nodes[*d] to target
            // swap nodes[*d] with nodes[destination_to_index[nodes[*d].target]]
            //ll a = nodes[*d].index; // this just equals (*d)
            ll b = destination_to_index[nodes[w].target]; //nodes[destination_to_index[nodes[*d].target]].index;
            ans.pb(mp(nodes[w].index, nodes[b].index));
            swap(nodes[w].target, nodes[b].target);

            while (nodes[w].target == nodes[w].destination) {
                d++;
                if (d == n) break;
                w = destination_to_index[d];
            }
        }
    }

    // consider functional graph on nodes:
    // edge a-->b iff a.target == b.destination
    return (d == n);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    s.resize(n);
    mek.resize(m);
    rep(i, 0, n) s[i] = S[i];
    rep(i, 0, m) mek[i] = mp(X[i], Y[i]);

    vpll ans;

    ll lowr = -1;
    ll highr = m;
    while (lowr + 1 < highr) {
        ll r = (lowr + highr + 1) / 2;
        //cout << "[" << lowr << ", " << highr << "] -> " << r << endl;
        if (solve(r, ans)) {
            highr = r;
            //cout << "high" << endl;
        } else {
            lowr = r;
            //cout << "low" << endl;
        }
        ans.clear();
    }

    solve(highr, ans);
    rep(i, 0, highr) {
        P[i] = (int) ans[i].first;
        Q[i] = (int) ans[i].second;
    }
    return (int) highr;
	// return R
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 2 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 1 ms 852 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Correct 1 ms 852 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 1 ms 596 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 246 ms 40336 KB Output is correct
16 Correct 248 ms 40956 KB Output is correct
17 Correct 295 ms 42448 KB Output is correct
18 Correct 123 ms 41552 KB Output is correct
19 Correct 210 ms 43512 KB Output is correct
20 Correct 217 ms 44164 KB Output is correct
21 Correct 221 ms 44136 KB Output is correct
22 Correct 247 ms 37992 KB Output is correct
23 Correct 265 ms 43688 KB Output is correct
24 Correct 293 ms 43276 KB Output is correct
25 Correct 298 ms 42808 KB Output is correct
26 Correct 213 ms 44036 KB Output is correct
27 Correct 200 ms 43416 KB Output is correct
28 Correct 278 ms 43288 KB Output is correct
29 Correct 302 ms 43016 KB Output is correct
30 Correct 161 ms 43704 KB Output is correct
31 Correct 290 ms 43660 KB Output is correct
32 Correct 265 ms 42552 KB Output is correct
33 Correct 291 ms 43096 KB Output is correct
34 Correct 269 ms 43028 KB Output is correct
35 Correct 219 ms 42808 KB Output is correct
36 Correct 106 ms 43684 KB Output is correct
37 Correct 323 ms 44212 KB Output is correct
38 Correct 281 ms 42808 KB Output is correct
39 Correct 278 ms 42936 KB Output is correct