oj.uz

Submission #516276

# Submission time Handle Problem Language Result Execution time Memory
516276 2022-01-21T01:44:22 Z Sorting Speedrun (RMI21_speedrun) C++17
100 / 100
 224 ms 944 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 944 KB Output is correct
2 Correct 135 ms 820 KB Output is correct
3 Correct 212 ms 808 KB Output is correct
4 Correct 200 ms 700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 660 KB Output is correct
2 Correct 189 ms 696 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 716 KB Output is correct
2 Correct 95 ms 700 KB Output is correct
3 Correct 102 ms 704 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 728 KB Output is correct
2 Correct 150 ms 700 KB Output is correct
3 Correct 219 ms 668 KB Output is correct
4 Correct 194 ms 700 KB Output is correct
5 Correct 206 ms 660 KB Output is correct
6 Correct 192 ms 704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 712 KB Output is correct
2 Correct 184 ms 704 KB Output is correct
3 Correct 200 ms 668 KB Output is correct
4 Correct 175 ms 716 KB Output is correct
5 Correct 130 ms 688 KB Output is correct
6 Correct 224 ms 732 KB Output is correct
7 Correct 166 ms 684 KB Output is correct