Submission #770637

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

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


// dijkstra, pq ?

pii best_dfs(int node, int entered = 0)
{
    if (when_ind_fixed[node] < entered) return {INF, 0};
    
    int ret_node = INF;
    int ret_time = entered; // !0
    if (when_ind_fixed[node] == INF) ret_node = node;

    rep(i,0,graph[node].size())
    {
        if (max(graph[node][i], node) > entered && graph[node][i] < ret_node && max(graph[node][i], node) <= when_ind_fixed[node])
        {
            pii alt_ret = best_dfs(graph[node][i], max(graph[node][i], node));
            if (alt_ret.first < ret_node) {
                ret_node = alt_ret.first;
                ret_time = alt_ret.second;
            }
        }
    }

    pii ret = {ret_node, ret_time};
    return ret;
}


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);
    }

    // rep(i, 1, n + 1){
    //     cerr << "node " << i << "\n";
    //     rep(j, 0, graph[i].size()) {
    //         cerr << graph[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }

    // edges.assign(n + 1, true);
    eend.assign(n + 1, -1);

    rep(i,1,n + 1) // n ?
    {
        pii reti = best_dfs(start[i]);
        //cerr << reti.first << " " << reti.second << "\n";
        assert(reti.first != 300000);
        when_ind_fixed[reti.first] = reti.second;
        eend[reti.first] = i; 
    }

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

Compilation message (stderr)

swap.cpp: In function 'pii best_dfs(int, int)':
swap.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int i = (a); i < (b); i++)
      |                                       ^
swap.cpp:32:5: note: in expansion of macro 'rep'
   32 |     rep(i,0,graph[node].size())
      |     ^~~

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