oj.uz

Submission #1011207

# Submission time Handle Problem Language Result Execution time Memory
1011207 2024-06-30T05:48:59 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
100 / 100
 95 ms 12496 KB 
#include "doll.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 1e9;

int n, m, cnt;
std::vector <int> a, c, x, y;

int build(int l, int r, int excess)
{
    if (r < excess)
    {
        return -1;
    }

    if (l == r)
    {
        return 0;
    }

    int node = ++cnt;
    x.push_back(0);
    y.push_back(0);
    int mid = l + r >> 1;
    x[node - 1] = build(l, mid, excess);
    y[node - 1] = build(mid + 1, r, excess);
    return -node;
}

bool state[MAXN];
bool push(int node, int value)
{
    if (state[node] ? (y[node - 1] == -1) : (x[node - 1] == -1))
    {
        state[node] ^= 1;
        return false;
    }
    
    if (state[node] ? (y[node - 1] == 0) : (x[node - 1] == 0))
    {
        if (state[node]) y[node - 1] = value;
        else x[node - 1] = value;
        state[node] ^= 1;
        return true;
    }

    if (state[node])
    {
        bool res = push(-y[node - 1], value);
        state[node] ^= 1;
        return res;
    } else
    {
        bool res = push(-x[node - 1], value);
        state[node] ^= 1;
        return res;
    }
}

void create_circuit(int M, std::vector <int> A)
{
    a = A;
    m = M;
    a.push_back(0);
    int bits = 0;
    int n = a.size();
    while ((1 << bits) < n)
    {
        bits++;
    }

    build(0, (1 << bits) - 1, (1 << bits) - n);
    for (int i = 0 ; i < n ; ++i)
    {
        while (!push(1, a[i]));
    }

    std::vector <int> c(m + 1, -1);
    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'int build(int, int, int)':
doll.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 29 ms 5060 KB Output is correct
3 Correct 24 ms 4996 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 44 ms 7136 KB Output is correct
7 Correct 0 ms 604 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 29 ms 5060 KB Output is correct
3 Correct 24 ms 4996 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 44 ms 7136 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 57 ms 8064 KB Output is correct
9 Correct 59 ms 8572 KB Output is correct
10 Correct 89 ms 12496 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 29 ms 5060 KB Output is correct
3 Correct 24 ms 4996 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 1628 KB Output is correct
6 Correct 44 ms 7136 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 57 ms 8064 KB Output is correct
9 Correct 59 ms 8572 KB Output is correct
10 Correct 89 ms 12496 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 11984 KB Output is correct
15 Correct 57 ms 7536 KB Output is correct
16 Correct 87 ms 11528 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 83 ms 12044 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

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 348 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 444 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 54 ms 6436 KB Output is correct
3 Correct 61 ms 6516 KB Output is correct
4 Correct 84 ms 9756 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 54 ms 6436 KB Output is correct
3 Correct 61 ms 6516 KB Output is correct
4 Correct 84 ms 9756 KB Output is correct
5 Correct 79 ms 11008 KB Output is correct
6 Correct 81 ms 10800 KB Output is correct
7 Correct 88 ms 11012 KB Output is correct
8 Correct 95 ms 10616 KB Output is correct
9 Correct 51 ms 6772 KB Output is correct
10 Correct 79 ms 10536 KB Output is correct
11 Correct 73 ms 10032 KB Output is correct
12 Correct 48 ms 6776 KB Output is correct
13 Correct 51 ms 7280 KB Output is correct
14 Correct 49 ms 7392 KB Output is correct
15 Correct 50 ms 7284 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 44 ms 7052 KB Output is correct
18 Correct 51 ms 6860 KB Output is correct
19 Correct 51 ms 6864 KB Output is correct
20 Correct 84 ms 10288 KB Output is correct
21 Correct 84 ms 10036 KB Output is correct
22 Correct 83 ms 10048 KB Output is correct