oj.uz

Submission #154806

# Submission time Handle Problem Language Result Execution time Memory
154806 2019-09-24T18:23:51 Z darkkcyan Mechanical Doll (IOI18_doll) C++14
100 / 100
 162 ms 8768 KB 
/**
 * Author: Tran Quang Loc
 * Tue Sep 24 15:50:15 MSK 2019
 */

#include<bits/stdc++.h>
#include "doll.h"

using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

void create_circuit(int m, std::vector<int> a) {
    int n = len(a);
    vector<int> x, y;
    vector<int> groups(n, 0);
    int fake_root = INT_MIN;
    while (len(groups) > 1) {
        vector<int> new_groups;
        if (len(groups) & 1) {
            new_groups.push_back(~len(x));
            x.push_back(fake_root);
            y.push_back(groups[0]);
        }
        for (int i = len(groups) & 1; i + 1 < len(groups); i += 2) {
            new_groups.push_back(~len(x));
            x.push_back(groups[i]);
            y.push_back(groups[i + 1]);
        }
        swap(groups, new_groups);
    }
    
    int root = ~(len(x) - 1);
    replace(x.begin(), x.end(), fake_root, root);

    std::vector<int> c(m + 1, root);
    c[0] = a[0];
    if (n > 1) { 
        a.erase(a.begin(), a.begin() + 1);
        a.push_back(0);
        vector<int> states(len(x));
        rep(i, n) {
            int cur = ~(len(x) - 1), prev = cur;
            while (cur < 0) {
                prev = cur;
                cur = states[~cur] ? y[~cur] : x[~cur];
                states[~prev] ^= 1;
            }
            (states[~prev] ? x[~prev] : y[~prev]) = a[i];
        }
    } else {
        c[a[0]] = 0;
    }
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 4128 KB Output is correct
3 Correct 44 ms 3628 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 67 ms 5440 KB Output is correct
7 Correct 1 ms 204 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 51 ms 4128 KB Output is correct
3 Correct 44 ms 3628 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 67 ms 5440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 83 ms 6868 KB Output is correct
9 Correct 96 ms 6440 KB Output is correct
10 Correct 125 ms 8768 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 51 ms 4128 KB Output is correct
3 Correct 44 ms 3628 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1356 KB Output is correct
6 Correct 67 ms 5440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 83 ms 6868 KB Output is correct
9 Correct 96 ms 6440 KB Output is correct
10 Correct 125 ms 8768 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 119 ms 8132 KB Output is correct
15 Correct 80 ms 5096 KB Output is correct
16 Correct 137 ms 7828 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 139 ms 8412 KB Output is correct
21 Correct 2 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 212 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 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 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 5020 KB Output is correct
3 Correct 72 ms 4408 KB Output is correct
4 Correct 162 ms 6532 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 5020 KB Output is correct
3 Correct 72 ms 4408 KB Output is correct
4 Correct 162 ms 6532 KB Output is correct
5 Correct 118 ms 7552 KB Output is correct
6 Correct 123 ms 7124 KB Output is correct
7 Correct 115 ms 7340 KB Output is correct
8 Correct 118 ms 6896 KB Output is correct
9 Correct 81 ms 4408 KB Output is correct
10 Correct 116 ms 6728 KB Output is correct
11 Correct 114 ms 6528 KB Output is correct
12 Correct 87 ms 4360 KB Output is correct
13 Correct 79 ms 5776 KB Output is correct
14 Correct 76 ms 4852 KB Output is correct
15 Correct 77 ms 5000 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 75 ms 5264 KB Output is correct
18 Correct 69 ms 5288 KB Output is correct
19 Correct 71 ms 4308 KB Output is correct
20 Correct 111 ms 6608 KB Output is correct
21 Correct 121 ms 6540 KB Output is correct
22 Correct 117 ms 6532 KB Output is correct