oj.uz

Submission #770637

# Submission time Handle Problem Language Result Execution time Memory
770637 2023-07-01T14:50:24 Z Ellinor Swap (BOI16_swap) C++14
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -