Submission #770655

#	Time	Username	Problem	Language	Result	Execution time	Memory
770655		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<int> edges;

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


vector<int> go_dfs(int node, int entered, int find)
{
    if (when_ind_fixed[node] < entered) return {INF, 0, 0};
    
    int ret_node = INF;
    int ret_time = entered; // !0
    if (when_ind_fixed[node] == INF) ret_node = node;

    int ret_found = 0;
    if (find == node) ret_found = 1;

    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] && edges[max(graph[node][i], node)] != 2)
        {
            vector<int> alt_ret = go_dfs(graph[node][i], max(graph[node][i], node), find);
            if (alt_ret[0] < ret_node) {
                ret_node = alt_ret[0];
                ret_time = alt_ret[1];
                ret_found += alt_ret[2];

                if (find != node && ret_found == 1)
                {
                    edges[max(graph[node][i], node)] += 1;
                }
            }
        }
    }

    vector<int> ret = {ret_node, ret_time, ret_found};
    return ret;
}


// 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] && edges[max(graph[node][i], node)] != 2)
        {
            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, 0);
    eend.assign(n + 1, -1);

    rep(i,1,n + 1) // n ?
    {
        pii reti = best_dfs(start[i]);
        go_dfs(start[i], 0, reti.first);
        //cerr << reti[0] << " " << reti[1] << "\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";
}

// 20 , 18 17 15 9 19 20 13 16 10 8 14 12 7 5 11 3 6 1 4 2

Compilation message (stderr)

swap.cpp: In function 'std::vector<int> go_dfs(int, 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:33:5: note: in expansion of macro 'rep'
   33 |     rep(i,0,graph[node].size())
      |     ^~~
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:66:5: note: in expansion of macro 'rep'
   66 |     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