oj.uz

Submission #696704

# Submission time Handle Problem Language Result Execution time Memory
696704 2023-02-07T05:21:06 Z sharaelong Mechanical Doll (IOI18_doll) C++17
100 / 100
 115 ms 11400 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int rev(int x, int sz) {
    int k = 31 - __builtin_clz(sz);
    int ret = 0;
    for (int i=0; i<k; ++i) ret |= (1 << (k-1-i)) * ((x & (1 << i)) > 0);
    // cout << x << ' ' << sz << ' ' << ret << endl;
    return ret;
}

const int INF = 1e9;

int switch_cnt = 0;
vector<int> c, x, y;

int solve(int cnt, int lev) {
    // cout << l << ' ' << r << ' ' << lev << endl;
    int root = -switch_cnt-1;
    switch_cnt++;
    if (lev == 1) {
        x.push_back((cnt == 1 ? -1 : INF));
        y.push_back(INF);
        return root;
    }
    
    if (cnt > (1 << (lev-1))) {
        x.push_back(0);
        y.push_back(0);
        x[-root-1] = solve(cnt-(1<<(lev-1)), lev-1);
        y[-root-1] = solve(1<<(lev-1), lev-1);
    } else {
        x.push_back(-1);
        y.push_back(0);
        y[-root-1] = solve(cnt, lev-1);
    }
    return root;
}

void create_circuit(int m, vector<int> A) {
    int n = A.size();
    A.push_back(0);
    c.resize(m+1, -1);

    int lev = 0;
    while (n+1 > (1 << lev)) lev++;
    solve(n+1, lev);

    // for (int i: c) cout << i << ' ';
    // cout << endl;
    // for (int i: x) cout << i << ' ';
    // cout << endl;
    // for (int i: y) cout << i << ' ';
    // cout << endl;

    int curr = -1;
    int allocate_cnt = 0;
    vector<bool> state(x.size(), 0);
    while (curr != 0) {
        if (curr >= 0) curr = c[curr];
        else {
            int& nxt = (state[-curr-1] ? y[-curr-1] : x[-curr-1]);
            if (nxt == INF) {
                nxt = A[allocate_cnt++];
            }
            state[-curr-1] = !state[-curr-1];
            curr = nxt;
        }
        // cout << curr << endl;
    }
    
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 39 ms 4700 KB Output is correct
3 Correct 35 ms 4500 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 54 ms 6604 KB Output is correct
7 Correct 0 ms 300 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 39 ms 4700 KB Output is correct
3 Correct 35 ms 4500 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 54 ms 6604 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 73 ms 7488 KB Output is correct
9 Correct 79 ms 8028 KB Output is correct
10 Correct 115 ms 11400 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 39 ms 4700 KB Output is correct
3 Correct 35 ms 4500 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 54 ms 6604 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 73 ms 7488 KB Output is correct
9 Correct 79 ms 8028 KB Output is correct
10 Correct 115 ms 11400 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 115 ms 10884 KB Output is correct
15 Correct 69 ms 7000 KB Output is correct
16 Correct 103 ms 10636 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 105 ms 11024 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 5996 KB Output is correct
3 Correct 65 ms 5980 KB Output is correct
4 Correct 96 ms 9104 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 66 ms 5996 KB Output is correct
3 Correct 65 ms 5980 KB Output is correct
4 Correct 96 ms 9104 KB Output is correct
5 Correct 110 ms 10548 KB Output is correct
6 Correct 102 ms 10084 KB Output is correct
7 Correct 101 ms 10256 KB Output is correct
8 Correct 101 ms 9880 KB Output is correct
9 Correct 62 ms 5980 KB Output is correct
10 Correct 100 ms 9872 KB Output is correct
11 Correct 98 ms 9488 KB Output is correct
12 Correct 64 ms 6216 KB Output is correct
13 Correct 68 ms 6672 KB Output is correct
14 Correct 73 ms 6700 KB Output is correct
15 Correct 68 ms 6896 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 59 ms 6556 KB Output is correct
18 Correct 66 ms 6236 KB Output is correct
19 Correct 69 ms 6216 KB Output is correct
20 Correct 99 ms 9744 KB Output is correct
21 Correct 99 ms 9456 KB Output is correct
22 Correct 98 ms 9464 KB Output is correct