oj.uz

Submission #601627

# Submission time Handle Problem Language Result Execution time Memory
601627 2022-07-22T08:46:28 Z Mazaalai Mechanical Doll (IOI18_doll) C++17
100 / 100
 172 ms 12188 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define pb push_back
#define ff first
#define ss second
using namespace std;
using VI = vector <int>;
using PII = pair <int, int>;
int n, m, p = 1;
const int N = 4e5;
VI c, x(N), y(N), state(N);
int switchNo;
int generate(int l, int r) {
    if (r < p-n-1) {
        return -1;
    }
    if (l == r) {
        return 0; // up or down
    }
    
    int mid = (l+r)>>1, curNode = ++switchNo;
    x[curNode] = generate(l, mid);
    y[curNode] = generate(mid+1, r);
    return -curNode;
}
void addPos(int pos, int v) { // removes n zero
    int& nx = (state[-pos] ? y[-pos] : x[-pos]); state[-pos] ^= 1;
    if (nx == 0) {
        nx = v;
        return;
    }
    return addPos(nx, v);
}
void create_circuit(int M, vector<int> nums) {
    m = M;
    n = sz(nums);
    c = VI(m+1, -1);
    while(p < n+1) p *= 2;
    switchNo = 0;
    generate(0, p-1);
    for (int i = 0; i < n; i++) addPos(-1, nums[i]);
    addPos(-1, 0);
    for (int i = 0; i < switchNo; i++) {
        x[i] = x[i+1];
        y[i] = y[i+1];
    }
    x.resize(switchNo);
    y.resize(switchNo);
    // for (int i = 0; i < sz(x); i++) cout << i+1 << ": " << x[i] << ',' << y[i] << '\n';
    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4980 KB Output is correct
2 Correct 47 ms 8156 KB Output is correct
3 Correct 42 ms 7768 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 17 ms 6100 KB Output is correct
6 Correct 69 ms 8988 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4980 KB Output is correct
2 Correct 47 ms 8156 KB Output is correct
3 Correct 42 ms 7768 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 17 ms 6100 KB Output is correct
6 Correct 69 ms 8988 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 97 ms 9472 KB Output is correct
9 Correct 97 ms 9808 KB Output is correct
10 Correct 149 ms 12052 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 5008 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4980 KB Output is correct
2 Correct 47 ms 8156 KB Output is correct
3 Correct 42 ms 7768 KB Output is correct
4 Correct 2 ms 5016 KB Output is correct
5 Correct 17 ms 6100 KB Output is correct
6 Correct 69 ms 8988 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 97 ms 9472 KB Output is correct
9 Correct 97 ms 9808 KB Output is correct
10 Correct 149 ms 12052 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 5008 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 126 ms 11704 KB Output is correct
15 Correct 84 ms 9404 KB Output is correct
16 Correct 172 ms 11876 KB Output is correct
17 Correct 3 ms 5012 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5016 KB Output is correct
20 Correct 134 ms 12188 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 4 ms 5008 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 4 ms 5008 KB Output is correct
5 Correct 4 ms 5008 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 89 ms 8068 KB Output is correct
3 Correct 89 ms 8076 KB Output is correct
4 Correct 124 ms 9628 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Correct 89 ms 8068 KB Output is correct
3 Correct 89 ms 8076 KB Output is correct
4 Correct 124 ms 9628 KB Output is correct
5 Correct 124 ms 10348 KB Output is correct
6 Correct 147 ms 10180 KB Output is correct
7 Correct 135 ms 10372 KB Output is correct
8 Correct 161 ms 9920 KB Output is correct
9 Correct 76 ms 8080 KB Output is correct
10 Correct 136 ms 9868 KB Output is correct
11 Correct 160 ms 9632 KB Output is correct
12 Correct 92 ms 8076 KB Output is correct
13 Correct 83 ms 8312 KB Output is correct
14 Correct 85 ms 8412 KB Output is correct
15 Correct 99 ms 8604 KB Output is correct
16 Correct 6 ms 5076 KB Output is correct
17 Correct 97 ms 8076 KB Output is correct
18 Correct 82 ms 8080 KB Output is correct
19 Correct 106 ms 8072 KB Output is correct
20 Correct 148 ms 9824 KB Output is correct
21 Correct 127 ms 9620 KB Output is correct
22 Correct 165 ms 9640 KB Output is correct