oj.uz

Submission #1060818

# Submission time Handle Problem Language Result Execution time Memory
1060818 2024-08-16T00:06:35 Z ArthuroWich Mechanical Doll (IOI18_doll) C++17
54.4023 / 100
 111 ms 14056 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
struct node {
    int l = INT_MIN, r = INT_MIN, y = 0, valid = 1, d = 0;
};
int timer = 2, dep, vl, vr;
vector<int> x, y;
node tree[500005];
void build(int n, int d) {
    tree[n].d = d;
    if (dep-1 == d) {
        return;
    }
    tree[n].l = -timer;
    timer++;
    tree[n].r = -timer;
    timer++;
    build(-tree[n].l, d+1);
    build(-tree[n].r, d+1);
}
void find(int n, int d, int l, int r) {
    int m = (l+r)/2;
    if (dep-1 == d) {
        if (tree[n].y == 0) {
            vl = l;
            vr = l;
        } else {
            vl = r;
            vr = r;
        }
    } else {
        if (tree[n].y == 0) {
            find(-tree[n].l, d+1, l, m);
        } else {
            find(-tree[n].r, d+1, m+1, r);
        }
    }
}
void create(int n, int d, int v) {
    if (dep-1 == d) {
        if (tree[n].y == 0) {
            tree[n].l = v;
        } else {
            tree[n].r = v;
        }
    } else {
        if (tree[n].y == 0) {
            create(-tree[n].l, d+1, v);
        } else {
            create(-tree[n].r, d+1, v);
        }
    }
    tree[n].y ^= 1;
}
void clean(int n, int d) {
    if (dep-1 == d) {
        if (tree[n].l == INT_MIN && tree[n].r == INT_MIN) {
            tree[n].valid = 0;
        }
    } else {
        clean(-tree[n].l, d+1);
        clean(-tree[n].r, d+1);
        tree[n].valid |= tree[-tree[n].l].valid;
        tree[n].valid |= tree[-tree[n].r].valid;
    }
}
void create_circuit(int m, vector<int> a) {
    vector<int> d(m+1, 0);
    d[0] = a[0];
    if (a.size() == 1) {
        answer(d, x, y);
        return;
    }
    d[a[0]] = -1;
    for (int i : a) {
        d[i] = -1;
    }
    int n = a.size(), s;
    dep = ceil(log2(n));
    s = 1 << dep;
    build(1, 0);
    int acl = 1, acr = n-1;
    int j = 1;
    for (int i = 1; i < s; i++) {
        find(1, 0, 1, s);
        if (acr < vl) {
            create(1, 0, INT_MIN);
        } else {
            create(1, 0, a[j]);
            j++;
        }
    }
    create(1, 0, 0);
    clean(1, 0);
    int co = 1;
    vector<int> conv(s, 0);
    for (int i = 1; i < s; i++) {
        if (tree[i].valid == 0) {
            continue;
        }
        conv[i] = co;
        co++;
    }
    for (int i = 1; i < s; i++) {
        if (tree[i].valid == 0) {
            continue;
        }
        if (tree[i].l >= 0) {
            x.push_back(tree[i].l);
        } else if (tree[i].l == INT_MIN || tree[-tree[i].l].valid == 0) {
            x.push_back(-1);
        } else {
            x.push_back(-conv[-tree[i].l]);
        }
        if (tree[i].r >= 0) {
            y.push_back(tree[i].r);
        } else if (tree[i].r == INT_MIN || tree[-tree[i].r].valid == 0) {
            y.push_back(-1);
        } else {
            y.push_back(-conv[-tree[i].r]);
        }
    }
    answer(d, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:83:9: warning: unused variable 'acl' [-Wunused-variable]
   83 |     int acl = 1, acr = n-1;
      |         ^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 32 ms 5784 KB Output is correct
3 Incorrect 52 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 32 ms 5784 KB Output is correct
3 Incorrect 52 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 32 ms 5784 KB Output is correct
3 Incorrect 52 ms 7424 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
10.8005494248 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Correct 54 ms 7736 KB Output is correct
3 Partially correct 99 ms 12476 KB Output is partially correct
4 Partially correct 105 ms 13660 KB Output is partially correct

Subtask #6
33.6017093216 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Correct 54 ms 7736 KB Output is correct
3 Partially correct 99 ms 12476 KB Output is partially correct
4 Partially correct 105 ms 13660 KB Output is partially correct
5 Partially correct 106 ms 14056 KB Output is partially correct
6 Partially correct 108 ms 13760 KB Output is partially correct
7 Partially correct 111 ms 13752 KB Output is partially correct
8 Partially correct 107 ms 13756 KB Output is partially correct
9 Partially correct 99 ms 12476 KB Output is partially correct
10 Partially correct 105 ms 13676 KB Output is partially correct
11 Partially correct 105 ms 13584 KB Output is partially correct
12 Partially correct 104 ms 12396 KB Output is partially correct
13 Correct 56 ms 7876 KB Output is correct
14 Partially correct 107 ms 12428 KB Output is partially correct
15 Partially correct 98 ms 12448 KB Output is partially correct
16 Partially correct 3 ms 856 KB Output is partially correct
17 Correct 55 ms 7540 KB Output is correct
18 Correct 54 ms 7624 KB Output is correct
19 Partially correct 101 ms 12400 KB Output is partially correct
20 Partially correct 107 ms 13680 KB Output is partially correct
21 Partially correct 108 ms 13760 KB Output is partially correct
22 Partially correct 110 ms 13580 KB Output is partially correct