Submission #833896

#	Time	Username	Problem	Language	Result	Execution time	Memory
833896		Tigerpants	Sorting (IOI15_sorting)	C++17	0 / 100	3 ms	596 KiB

sorting

#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;
    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]);

        ll w;
        if (d < n) {
            w = destination_to_index[d];

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

        if (d == n) {
            ans.pb(mp(0, 0));
        } else {
            // 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);

            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
}

Compilation message (stderr)

sorting.cpp: In function 'bool solve(ll, vpll&)':
sorting.cpp:77:48: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             ll b = destination_to_index[nodes[w].target]; //nodes[destination_to_index[nodes[*d].target]].index;
      |                                                ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26