oj.uz

Submission #611870

# Submission time Handle Problem Language Result Execution time Memory
611870 2022-07-29T08:13:35 Z hibiki Mechanical Doll (IOI18_doll) C++11
53 / 100
 137 ms 18520 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

int pw2[32];
vector<int> nxt[100005], c, x, y;

int seat = -1;
int dfs(int val, int lv, int mlv, int head)
{
    if (lv == mlv)
    {
        if (nxt[head][val] == -1)
            return -seat;
        return nxt[head][val];
    }
    pair<int, int> ret;
    ret.f = dfs(val, lv + 1, mlv, head);
    ret.s = dfs(val + pw2[lv], lv + 1, mlv, head);
    if (lv)
    {
        x.pb(ret.f);
        y.pb(ret.s);
        return -sz(x);
    }
    else
    {
        x[seat - 1] = ret.f;
        y[seat - 1] = ret.s;
        return -seat;
    }
}

void create_circuit(int m, vector<int> a)
{
    int n = sz(a);
    pw2[0] = 1;
    for (int i = 1; i < 32; i++)
        pw2[i] = pw2[i - 1] * 2;

    nxt[0].pb(a[0]);
    for (int i = 0; i < n - 1; i++)
        nxt[a[i]].pb(a[i + 1]);
    nxt[a[n - 1]].pb(0);

    c.pb(nxt[0][0]);
    for (int i = 1; i <= m; i++)
    {
        if (nxt[i].empty())
        {
            c.pb(i);
            continue;
        }

        if (sz(nxt[i]) == 1)
        {
            c.pb(nxt[i][0]);
            continue;
        }

        int mlv = ceil(log2(sz(nxt[i])));
        int msz = pw2[mlv];

        vector<int> temp;
        for (int j = 0; j < msz - sz(nxt[i]); j++)
            temp.pb(-1);
        for (auto val : nxt[i])
            temp.pb(val);
        nxt[i] = temp;

        x.pb(-1);
        y.pb(-1);
        seat = sz(x);
        c.pb(dfs(0, 0, mlv, i));
    }

    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 41 ms 6860 KB Output is correct
3 Correct 22 ms 6564 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 17 ms 4164 KB Output is correct
6 Correct 31 ms 8532 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 41 ms 6860 KB Output is correct
3 Correct 22 ms 6564 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 17 ms 4164 KB Output is correct
6 Correct 31 ms 8532 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 67 ms 9660 KB Output is correct
9 Correct 69 ms 9716 KB Output is correct
10 Correct 96 ms 12332 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 41 ms 6860 KB Output is correct
3 Correct 22 ms 6564 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 17 ms 4164 KB Output is correct
6 Correct 31 ms 8532 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 67 ms 9660 KB Output is correct
9 Correct 69 ms 9716 KB Output is correct
10 Correct 96 ms 12332 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 91 ms 14040 KB Output is correct
15 Correct 66 ms 8528 KB Output is correct
16 Correct 104 ms 11296 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2648 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 100 ms 12800 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 1 ms 2648 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2652 KB Output is partially correct
2 Correct 40 ms 8852 KB Output is correct
3 Partially correct 92 ms 13928 KB Output is partially correct
4 Partially correct 77 ms 14340 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2652 KB Output is partially correct
2 Correct 40 ms 8852 KB Output is correct
3 Partially correct 92 ms 13928 KB Output is partially correct
4 Partially correct 77 ms 14340 KB Output is partially correct
5 Partially correct 137 ms 15820 KB Output is partially correct
6 Partially correct 126 ms 16952 KB Output is partially correct
7 Partially correct 106 ms 16628 KB Output is partially correct
8 Partially correct 127 ms 17568 KB Output is partially correct
9 Partially correct 67 ms 12268 KB Output is partially correct
10 Partially correct 106 ms 18520 KB Output is partially correct
11 Partially correct 98 ms 18180 KB Output is partially correct
12 Partially correct 69 ms 12976 KB Output is partially correct
13 Partially correct 64 ms 12220 KB Output is partially correct
14 Partially correct 68 ms 11836 KB Output is partially correct
15 Partially correct 71 ms 11512 KB Output is partially correct
16 Partially correct 4 ms 2900 KB Output is partially correct
17 Partially correct 54 ms 10820 KB Output is partially correct
18 Partially correct 58 ms 10768 KB Output is partially correct
19 Partially correct 59 ms 11472 KB Output is partially correct
20 Partially correct 91 ms 13748 KB Output is partially correct
21 Partially correct 92 ms 16056 KB Output is partially correct
22 Partially correct 74 ms 13140 KB Output is partially correct