oj.uz

Submission #795659

# Submission time Handle Problem Language Result Execution time Memory
795659 2023-07-27T12:29:02 Z anton Speedrun (RMI21_speedrun) C++17
100 / 100
 204 ms 904 KB 
#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;

vector<bool> get_bits(int id){
    vector<bool> res(10, 0);

    for(int i = 0; i<10; i++){
        res[i] = ((id & (1<<i))>0);
        ////cout<<(id & (1<<i))<<endl;
    }
    return res;
}

void mySetHint(int i, int j, bool b){
    int b2;
    if(b){
        b2 =1;
    }
    else{
        b2 =0;
    }
    //cout<<"setting "<<i<<" "<<j<<" "<<b2<<endl;
    setHint(i, j, b);
}

void set_anc(int u, int anc){
    auto anc_b = get_bits(anc);
    for(int i = 0; i<10; i++){
        mySetHint(u, i+1, anc_b[i]);
    }
}
void set_down(int u, int v){
    auto v_b = get_bits(v);
    for(int i = 10; i<20; i++){
        mySetHint(u, i+1, v_b[i-10]);
    }
}

void dfs(int u, int anc, vector<vector<int>>& adj, vector<int>& order){
    set_anc(u, anc);

    if(order.size()>0){
        set_down(order.back(), u);
    }
    order.push_back(u);

    for(auto e: adj[u]){
        if(e!=anc){
            dfs(e, u, adj, order);
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    //cout<<"hello"<<endl;
    vector<vector<int>> adj(N+1);
    vector<int> order;

    for(int i = 1; i<=N-1; i++){
        int a =A[i];
        int b = B[i];

        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    //cout<<"hello"<<endl;

    dfs(1, 1, adj, order);

    set_down(order.back(), order.back());
}

int get_up(){
    int res =0;

    for(int i = 0; i<10; i++){
        if(getHint(i+1)){
            res += (1<<i);
        }
    }
    return res;
}

int get_down(){
    int res =0;

    for(int i = 0; i<10; i++){
        if(getHint(i+11)){
            res += (1<<i);
        }
    }
    return res;
}

bool myGoTo(int i){
    bool res = goTo(i);
    //cout<<"go "<<i<<" "<<res<<endl;
    return res;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    int cur =start;

    while(get_up()!=cur){
        cur = get_up();
        myGoTo(cur);
    }

    for(int i = 0; i<N; i++){
        int next = get_down();
        if(next!=cur){
            while(!myGoTo(next)){
                myGoTo(get_up());
            }
        }
        cur = next;
    }
}

Compilation message

speedrun.cpp: In function 'void mySetHint(int, int, bool)':
speedrun.cpp:16:9: warning: variable 'b2' set but not used [-Wunused-but-set-variable]
   16 |     int b2;
      |         ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 720 KB Output is correct
2 Correct 147 ms 748 KB Output is correct
3 Correct 185 ms 732 KB Output is correct
4 Correct 184 ms 732 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 736 KB Output is correct
2 Correct 137 ms 688 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 772 KB Output is correct
2 Correct 150 ms 772 KB Output is correct
3 Correct 134 ms 732 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 672 KB Output is correct
2 Correct 120 ms 728 KB Output is correct
3 Correct 155 ms 904 KB Output is correct
4 Correct 152 ms 828 KB Output is correct
5 Correct 74 ms 732 KB Output is correct
6 Correct 121 ms 736 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 736 KB Output is correct
2 Correct 177 ms 744 KB Output is correct
3 Correct 117 ms 804 KB Output is correct
4 Correct 174 ms 728 KB Output is correct
5 Correct 123 ms 832 KB Output is correct
6 Correct 124 ms 792 KB Output is correct
7 Correct 173 ms 732 KB Output is correct