Submission #772276

#	Time	Username	Problem	Language	Result	Execution time	Memory
772276		Ellinor	Swap (BOI16_swap)	C++14	100 / 100	65 ms	5240 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<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);

    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) {
                // when_ind_fixed[start[i]/2] >= max(start[i], other) -> true , hm 0 , hm start[i] / 2
                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 (j < calcs.size()) {
                        // j < n
                        if (calc(calcs[j])) {
                            oth_min = calcs[j];
                            break;
                        }
                        else j++;
                    }
                }
            }
        }

        int here_min = INF;

        if (edges_up[start[i]]) // 1
        {
            calcs = {};
            calcs.pb(start[i]);

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

        if (here_min == INF && oth_min == INF) {
            //cerr << i << "\n";
            // rep(j,1,n+1){
            //     cerr << eend[j] << " ";
            // }
            // cerr << "\n";
        }
        assert(!(here_min == INF && oth_min == INF));

        //cerr << "REP " << i << " here: " << here_min << " oth: " << oth_min << "\n";

        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)
            {
                //assert(j > stop);
                edges_up[j] = false;
                j = j / 2;
            }
        }

        else
        {
            edges_up[start[i]] = false;

            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)
            {
                //assert(j > stop);
                edges_up[j] = false;
                j = j / 2;
            }
        }

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

        // eend[] = i;

        //cerr << "REP end " << i << "\n";
        //cerr << "edges_up:\n";
        // rep(j,0,n+1){
        //     cerr << edges_up[j] << " ";
        // }
        // cerr << "\n";
    }

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

Compilation message (stderr)

swap.cpp: In function 'int32_t main()':
swap.cpp:102:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                     while (j < calcs.size()) {
      |                            ~~^~~~~~~~~~~~~~
swap.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             while (j < calcs.size()) {
      |                    ~~^~~~~~~~~~~~~~

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