Submission #516276

#	Time	Username	Problem	Language	Result	Execution time	Memory
516276		Sorting	Speedrun (RMI21_speedrun)	C++17	100 / 100	224 ms	944 KiB

speedrun

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

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

const int N = 1000 + 3;

vector<int> adj[N], order;
int p[N], n;

void setNumber(int i, bool second, int num){
    for(int j = 0; j < 10; ++j)
        setHint(i, 10 * second + j + 1, (num >> j) & 1);
}

void dfs(int u, int par){
    order.push_back(u);
    p[u] = par;

    for(int to: adj[u]){
        if(to == par) continue;

        dfs(to, u);
    }
}

void assignHints(int subtask, int _n, int a[], int b[]){
    setHintLen(20);

    n = _n;

    for(int i = 1; i < n; ++i){
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    dfs(1, 1);

    for(int i = 0; i < n; ++i){
        int x = order[i];
        setNumber(x, 0, p[x]);
        if(i == n - 1) setNumber(x, 1, x);
        else setNumber(x, 1, order[i + 1]);
    }
}

int getNumber(bool second){
    int result = 0;
    for(int j = 0; j < 10; ++j)
        result += ((int)getHint(10 * second + j + 1)) << j;
    return result;
}

void speedrun(int subtask, int _n, int start){
    n = _n;

    while(start != 1)
        goTo(start = getNumber(0));

    while(getNumber(1) != start){
        int nxt = getNumber(1);
        while(!goTo(nxt))
            goTo(start = getNumber(0));
        start = nxt;
    }
}

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