oj.uz

답안 #833935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833935 2023-08-22T09:36:38 Z Tigerpants 정렬하기 (IOI15_sorting) C++17
54 / 100
 2 ms 992 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 {
            // 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 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 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 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 1 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 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 2 ms 980 KB Output is correct
22 Correct 1 ms 992 KB Output is correct
23 Correct 2 ms 980 KB Output is correct
24 Correct 2 ms 980 KB Output is correct
25 Correct 2 ms 980 KB Output is correct
26 Correct 2 ms 980 KB Output is correct
27 Correct 2 ms 980 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Incorrect 2 ms 676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Incorrect 2 ms 676 KB Output isn't correct
4 Halted 0 ms 0 KB -