oj.uz

Submission #363516

# Submission time Handle Problem Language Result Execution time Memory
363516 2021-02-06T10:30:28 Z mjhmjh1104 Mechanical Doll (IOI18_doll) C++14
100 / 100
 183 ms 10972 KB 
#include "doll.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool sw[400006];
int n, s;
vector<int> c, a, b;

bool goForward(int &x) {
    if (x >= 0) {
        if (c[x] == -2e9) return false;
        x = c[x];
    } else {
        if (!sw[-x - 1]) {
            if (a[-x - 1] == -2e9) return false;
            sw[-x - 1] = true;
            x = a[-x - 1];
        } else {
            if (b[-x - 1] == -2e9) return false;
            sw[-x - 1] = false;
            x = b[-x - 1];
        }
    }
    return true;
}

void create_circuit(int m, vector<int> A) {
    n = (int)A.size();
    c.resize(m + 1);
    for (int i = 0; i < m + 1; i++) c[i] = -2e9;
    n++;
    int bit = ceil(log2(n));
    int sw_size = 1 << bit;
    int left = sw_size - n;
    vector<pair<int, int>> sw_cnt, nsw_cnt;
    sw_cnt.push_back({ 0, -1 });
    for (int t = bit - 1; t >= 0; t--) {
        bool rem = false;
        if (left >= 1 << t) {
            left -= 1 << t;
            rem = true;
        }
        nsw_cnt.clear();
        for (int i = 0; i < (int)sw_cnt.size(); i++) {
            if (sw_cnt[i].second == -1) c[sw_cnt[i].first] = -s - 1;
            else if (sw_cnt[i].second == 0) a[sw_cnt[i].first] = -s - 1;
            else b[sw_cnt[i].first] = -s - 1;
            if (rem) {
                nsw_cnt.push_back({ s, 1 });
                a.push_back(-1);
                b.push_back(-2e9);
                rem = false;
            } else {
                nsw_cnt.push_back({ s, 0 });
                nsw_cnt.push_back({ s, 1 });
                a.push_back(-2e9);
                b.push_back(-2e9);
            }
            s++;
        }
        sw_cnt = nsw_cnt;
    }
    for (int i = 0; i <= m; i++) c[i] = -1;
    n--;
    A.push_back(0);
    int curr = 0;
    for (int i = 0; i <= n; i++) {
        while (goForward(curr)) ;
        if (curr >= 0) c[curr] = A[i];
        else if (!sw[-curr - 1]) {
            a[-curr - 1] = A[i];
            sw[-curr - 1] = true;
        } else {
            b[-curr - 1] = A[i];
            sw[-curr - 1] = false;
        }
        curr = A[i];
    }
    answer(c, a, b);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 5288 KB Output is correct
3 Correct 51 ms 4744 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 76 ms 6236 KB Output is correct
7 Correct 1 ms 224 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 5288 KB Output is correct
3 Correct 51 ms 4744 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 76 ms 6236 KB Output is correct
7 Correct 1 ms 224 KB Output is correct
8 Correct 107 ms 8288 KB Output is correct
9 Correct 99 ms 9112 KB Output is correct
10 Correct 170 ms 10972 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 54 ms 5288 KB Output is correct
3 Correct 51 ms 4744 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 76 ms 6236 KB Output is correct
7 Correct 1 ms 224 KB Output is correct
8 Correct 107 ms 8288 KB Output is correct
9 Correct 99 ms 9112 KB Output is correct
10 Correct 170 ms 10972 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 164 ms 10612 KB Output is correct
15 Correct 101 ms 7756 KB Output is correct
16 Correct 173 ms 10440 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 178 ms 10776 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 248 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 89 ms 7104 KB Output is correct
3 Correct 90 ms 7032 KB Output is correct
4 Correct 143 ms 9836 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 89 ms 7104 KB Output is correct
3 Correct 90 ms 7032 KB Output is correct
4 Correct 143 ms 9836 KB Output is correct
5 Correct 139 ms 10252 KB Output is correct
6 Correct 180 ms 10056 KB Output is correct
7 Correct 142 ms 10192 KB Output is correct
8 Correct 134 ms 10012 KB Output is correct
9 Correct 92 ms 7096 KB Output is correct
10 Correct 144 ms 9928 KB Output is correct
11 Correct 134 ms 9840 KB Output is correct
12 Correct 98 ms 7312 KB Output is correct
13 Correct 96 ms 7676 KB Output is correct
14 Correct 96 ms 7624 KB Output is correct
15 Correct 96 ms 7744 KB Output is correct
16 Correct 3 ms 516 KB Output is correct
17 Correct 83 ms 6592 KB Output is correct
18 Correct 95 ms 7244 KB Output is correct
19 Correct 109 ms 7296 KB Output is correct
20 Correct 146 ms 9896 KB Output is correct
21 Correct 183 ms 9836 KB Output is correct
22 Correct 139 ms 9844 KB Output is correct