Submission #1227755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227755		acoatoitgs	Speedrun (RMI21_speedrun)	C++17	0 / 100	0 ms	468 KiB

speedrun

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long

void setHintLen (int l);
void setHint (int i, int j, bool b);
int getLength ();
bool getHint (int j);
bool goTo(int x);

void assignHints (int subtask , int N, int A[], int B[])
{
    setHintLen(20);
    if(N == 1) return;

    vector<vector<ll>> adj(N);
    for(ll i = 1; i < N; i++)
    {
        adj[--A[i]].emplace_back(--B[i]);
        adj[B[i]].emplace_back(A[i]);
    }

    srand(time(0));
    // ll root = 2;
    ll root = rand()%N;
    
    auto setBit = [&](ll node, ll val, bool b) -> void
    {
        node++;
        val++;
        // cout << "Setting " << node << " " << val << " " << b << "\n";
        ll offset = (b ? 10 : 0);
        for(ll i = offset; i < 10+offset; i++)
        {
            setHint(node, i, val&(1ll << (i-offset)));
        }
    };

    stack<ll> q;
    q.push(root);
    function<void(ll, ll)> dfs = [&](ll node, ll parent) -> void
    {
        // cout << node << " " << parent << "\n";
        if(parent != -1)
        {
            adj[node].erase(find(adj[node].begin(), adj[node].end(), parent));
            setBit(node, parent, 0);
        }

        if(adj[node].size() == 0)
        {
            setBit(node, q.top(), 1);
            q.pop();
            return;
        }

        setBit(node, adj[node][0], 1);
        for(int i = 0; i < adj[node].size()-1; i++)
        {
            q.push(adj[node][i+1]);
            dfs(adj[node][i], node);
        }

        dfs(adj[node].back(), node);  
    };

    // cout << "Root: " << root+1 << "\n";

    setBit(root, 1022, 0);
    setBit(root, adj[root][0], 1);

    dfs(root, -1);
    assert(q.empty());
}

void speedrun (int subtask , int N, int start )
{
    if(N == 1) return;

    auto readVal = [&](bool v) -> ll
    {
        ll offset = (v ? 10 : 0);
        ll val = 0;
        for(ll i = offset; i < 10+offset; i++)
        {
            val += getHint(i)*(1ll<<(i-offset));
        }
        return val;
    };

    //get to root
    ll v;
    ll node = start;
    while((v = readVal(0)) != 1023)
    {
        // cout << node << " " << v << "\n";
        assert(goTo(v));
        node = v;
    }

    ll root = node;

    stack<ll> parent;
    ll nx = readVal(1);
    while(nx != root)
    {
        // cout << node << " " << nx << "\n";
        if(goTo(nx))
        {
            parent.push(node);
            node = nx;
            nx = readVal(1);
        }
        else
        {
            goTo(parent.top());
            node = parent.top();
            parent.pop();
        }
    }   


    return;
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40