oj.uz

Submission #286365

# Submission time Handle Problem Language Result Execution time Memory
286365 2020-08-30T10:29:51 Z ne4eHbKa Mechanical Doll (IOI18_doll) C++17
100 / 100
 167 ms 7908 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

namespace solution {

vi c, x, y;
int s;
vector<bool> q;

int swicch(int l, int r) {
    int p = l + r >> 1;
    int i = s++;
    x.push_back(0);
    y.push_back(0);
    q.push_back(false);
    if(l + r == 2) {
        if(l) x[i] = -1;
        return -(i + 1);
    }
    if(l >= p) {
        x[i] = -1;
        y[i] = swicch(l - p, r);
        return -(i + 1);
    }
    x[i] = swicch(l, r - p);
    y[i] = swicch(0, p);
    return -(i + 1);
}

void push(int i, int v) {
    int &j = (q[i] ? y[i] : x[i]);
    q[i] = !q[i];
    if(!j) {j = v; return;}
    push(-(j + 1), v);
}

}

void create_circuit (int m, vi a) {
    using namespace solution;
    int n = a.size();
    s = 0;
    x.clear(); x.reserve(n * 4);
    y.clear(); y.reserve(n * 4);
    q.clear(); q.reserve(n * 4);
    if(n == 1) {
        c.assign(m + 1, 0);
        c[0] = a[0];
        answer(c, x, y);
        return;
    }
    c.assign(m + 1, -1);
    c[0] = a[0];
    int e = 0;
    for(; __builtin_popcount(e + n) > 1; ++e);
    swicch(e, n);
    for(int i = 1; i < n; ++i) push(0, a[i]);
    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int solution::swicch(int, int)':
doll.cpp:13:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int p = l + r >> 1;
      |             ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 3540 KB Output is correct
3 Correct 43 ms 3168 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 66 ms 4580 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 50 ms 3540 KB Output is correct
3 Correct 43 ms 3168 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 66 ms 4580 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 83 ms 5200 KB Output is correct
9 Correct 101 ms 5692 KB Output is correct
10 Correct 129 ms 7908 KB Output is correct
11 Correct 1 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 50 ms 3540 KB Output is correct
3 Correct 43 ms 3168 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 66 ms 4580 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 83 ms 5200 KB Output is correct
9 Correct 101 ms 5692 KB Output is correct
10 Correct 129 ms 7908 KB Output is correct
11 Correct 1 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 136 ms 7644 KB Output is correct
15 Correct 81 ms 4852 KB Output is correct
16 Correct 142 ms 7444 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 138 ms 7684 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 204 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 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 72 ms 4396 KB Output is correct
3 Correct 78 ms 4424 KB Output is correct
4 Correct 125 ms 6576 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 72 ms 4396 KB Output is correct
3 Correct 78 ms 4424 KB Output is correct
4 Correct 125 ms 6576 KB Output is correct
5 Correct 151 ms 7252 KB Output is correct
6 Correct 146 ms 7060 KB Output is correct
7 Correct 122 ms 7172 KB Output is correct
8 Correct 167 ms 6932 KB Output is correct
9 Correct 78 ms 4396 KB Output is correct
10 Correct 127 ms 6768 KB Output is correct
11 Correct 125 ms 6580 KB Output is correct
12 Correct 86 ms 4432 KB Output is correct
13 Correct 76 ms 4632 KB Output is correct
14 Correct 83 ms 4792 KB Output is correct
15 Correct 92 ms 4892 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 72 ms 4420 KB Output is correct
18 Correct 73 ms 4432 KB Output is correct
19 Correct 78 ms 4432 KB Output is correct
20 Correct 143 ms 6624 KB Output is correct
21 Correct 119 ms 6596 KB Output is correct
22 Correct 136 ms 6564 KB Output is correct