oj.uz

Submission #554496

# Submission time Handle Problem Language Result Execution time Memory
554496 2022-04-28T14:01:47 Z kevinxiehk Mechanical Doll (IOI18_doll) C++17
100 / 100
 309 ms 31112 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
using namespace std;
int cnt = -1;
pair<int, int> lr[400005];
map<int, int> hv;
int need = 0;
int arr[400005];
vector<int> add;
int dfs(int lay, int tc, int lef) {
    if(lay == need) {
        add.pb(tc + 1);
        return tc + 1;
    }
    int k = (1 << (need - lay - 1));
    int thisid = cnt; cnt--;
    // cerr << thisid << ' ' << lef << '\n';
    if(lef > k) {
        lr[-thisid].fi = dfs(lay + 1, tc, k);
        lr[-thisid].se = dfs(lay + 1, tc + (1 << lay), lef - k);
    }
    else {
        lr[-thisid] = mp(-1, dfs(lay + 1, tc + (1 << lay), lef));
    }
    return thisid;
}
void create_circuit(int m, vector<int> a) {
    int n = a.size();
    vector<int> c(m + 1);
    c[0] = a[0];
    a.pb(0);
    vector<int> aa;
    for(int i = 1; i <= n; i++) aa.pb(a[i]);
    for(int i = 1; i <= m; ++i) {
        c[i] = -1;
    }
    vector<int> l, r;
    if(n == 1) {
        l.pb(-1);
        r.pb(0);
        answer(c, l, r);
        return;
    }
    while((1 << need) < n) need++;
    dfs(0, 0, n);
    for(int i = 1; i < -cnt; i++) hv[-i] = -i;
    sort(add.begin(), add.end());
    for(int i = 0; i < n; i++) hv[add[i]] = aa[i];
    // for(int i = 0; i < n; i++) hv[add[i]] = add[i];
    for(int i = 1; i < -cnt; i++) {
        l.pb(hv[lr[i].fi]);
        r.pb(hv[lr[i].se]);
        // cerr << -i << ' ' << hv[lr[i].fi] << ' ' << hv[lr[i].se] << '\n';
    }
    answer(c, l, r);
    return;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 10800 KB Output is correct
3 Correct 68 ms 10496 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 132 ms 15692 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 10800 KB Output is correct
3 Correct 68 ms 10496 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 132 ms 15692 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 159 ms 21608 KB Output is correct
9 Correct 214 ms 20984 KB Output is correct
10 Correct 289 ms 31112 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 73 ms 10800 KB Output is correct
3 Correct 68 ms 10496 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 132 ms 15692 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 159 ms 21608 KB Output is correct
9 Correct 214 ms 20984 KB Output is correct
10 Correct 289 ms 31112 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 287 ms 30736 KB Output is correct
15 Correct 171 ms 20120 KB Output is correct
16 Correct 271 ms 30500 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 281 ms 30828 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 155 ms 19792 KB Output is correct
3 Correct 155 ms 18740 KB Output is correct
4 Correct 282 ms 28708 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 155 ms 19792 KB Output is correct
3 Correct 155 ms 18740 KB Output is correct
4 Correct 282 ms 28708 KB Output is correct
5 Correct 309 ms 30444 KB Output is correct
6 Correct 289 ms 30244 KB Output is correct
7 Correct 274 ms 30208 KB Output is correct
8 Correct 273 ms 30020 KB Output is correct
9 Correct 142 ms 19632 KB Output is correct
10 Correct 288 ms 30128 KB Output is correct
11 Correct 262 ms 29868 KB Output is correct
12 Correct 140 ms 19756 KB Output is correct
13 Correct 142 ms 21160 KB Output is correct
14 Correct 170 ms 19948 KB Output is correct
15 Correct 142 ms 20052 KB Output is correct
16 Correct 4 ms 980 KB Output is correct
17 Correct 140 ms 20884 KB Output is correct
18 Correct 145 ms 21064 KB Output is correct
19 Correct 137 ms 19680 KB Output is correct
20 Correct 263 ms 29776 KB Output is correct
21 Correct 262 ms 29884 KB Output is correct
22 Correct 286 ms 29956 KB Output is correct