Submission #770774

#	Time	Username	Problem	Language	Result	Execution time	Memory
770774		Ellinor	Swap (BOI16_swap)	C++14	0 / 100	1076 ms	212 KiB

swap

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;
#define pb push_back
typedef pair<int, int> pii;

int INF = 3e5;

int n;

// graph
vector<vector<int>> graph;
vector<bool> edges_up;
vector<bool> edges_down;

vector<int> start;
vector<int> when_ind_fixed;
vector<int> eend;

vector<int> calcs;

bool calc(int node)
{
    //cerr << node << "\n";
    if (when_ind_fixed[node] == INF) return true;

    int left = node * 2;
    if (left < n + 1) {
        // cerr << "left " << left << "\n";
        // cerr << "ed_do " << edges_down[left] << "\n";
        // cerr << "fix " << when_ind_fixed[node] << "\n";
        if (edges_up[left] && when_ind_fixed[node] >= left) {
            //cerr << "pbl\n";
            calcs.pb(left);
        }
    }

    int right = node * 2 + 1;
    if (right < n + 1) {
        if (edges_up[right] && when_ind_fixed[node] >= right) {
            //cerr << "pbr\n";
            calcs.pb(right);
        }
    }

    return false;
}


int32_t main()
{
    // fast

    cin >> n;
    start.assign(n + 1, -1);

    int a;
    rep(i,1,n + 1){
        cin >> a;
        start[a] = i;
    }

    when_ind_fixed.assign(n + 1, INF);

    graph.assign(n + 1, {});
    rep(i,2,n + 1){
        graph[i / 2].pb(i);
        graph[i].pb(i / 2);
    }
    //

    edges_up.assign(n + 1, true);
    edges_down.assign(n + 1, true);
    eend.assign(n + 1, -1);

    // .

    rep(i,1,n + 1) // n ?
    {
        //cerr << "REP " << i << " !!!\n";

        int oth_min = INF;

        if (start[i] != 1)
        {
            int other;
            if (((start[i]/2)*2)+1 != start[i]) other = ((start[i]/2)*2)+1;
            else other = ((start[i]/2)*2);

            //cerr << "other " << other << "\n";

            if (when_ind_fixed[start[i]/2] == INF && edges_down[start[i]]) {

                when_ind_fixed[start[i]/2] = start[i];
                edges_down[start[i]] = false;

                eend[start[i]/2] = i;
                continue;
            }

            else if (other < n + 1) {
                if (edges_down[start[i]] && edges_up[other] && when_ind_fixed[start[i]/2] >= max(start[i], other)) {
                    calcs = {};
                    calcs.pb(other);

                    int j = 0;
                    while (true) {
                        if (calc(calcs[j])) {
                            oth_min = calcs[j];
                            break;
                        }
                        else j++;
                    }
                }
            }
        }

        int here_min;

        calcs = {};
        calcs.pb(start[i]);

        int j = 0;
        while (true) {
            if (calc(calcs[j])) {
                here_min = calcs[j];
                break;
            }
            else j++;
        }

        if (oth_min < here_min)
        {
            edges_down[start[i]] = false;
            //

            eend[oth_min] = i;
            when_ind_fixed[oth_min] = oth_min;

            int stop = start[i]/2;
            int j = oth_min;
            while (j != stop)
            {
                edges_up[j] = false;
                j = j / 2;
            }
        }

        else
        {
            eend[here_min] = i;
            when_ind_fixed[here_min] = here_min;
            if (here_min == start[i]) when_ind_fixed[here_min] = 0;
            // edges_down[here_min] = false; // hm

            int stop = start[i];
            int j = here_min;
            while (j != stop)
            {
                edges_up[j] = false;
                j = j / 2;
            }
        }

        // min oth_min, here_min , node / 2 rec edges, when_ind node

        // eend[] = i;
    }

    rep(i, 1, n + 1){
        cout << eend[i] << " ";
    }
    cout << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32