oj.uz

Submission #260911

# Submission time Handle Problem Language Result Execution time Memory
260911 2020-08-11T07:35:19 Z Alexa2001 Mechanical Doll (IOI18_doll) C++17
100 / 100
 190 ms 22256 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> x, y, c;
vector<bool> state;

int n, k, e, nodes = 1;


void create_tree(int node, int sz)
{
    if(sz == 2)
    {
        if(e & 1)
        {
            x[node] = 1;
            y[node] = 0;
            e ^= 1;
        }
        else x[node] = y[node] = 0;

        return;
    }

    if(e & (sz/2))
        x[node] = 1, e ^= (sz/2);
    else
    {
        x[node] = ++nodes;
        create_tree(nodes, sz/2);
    }

    y[node] = ++nodes;
    create_tree(nodes, sz/2);
}

void place(int number, int node = 1)
{
    if(state[node] == 0)
    {
        state[node] = 1;

        if(x[node] == 0)
        {
            x[node] = number;
            return;
        }
        else place(number, x[node]);
    }
    else
    {
        state[node] = 0;

        if(y[node] == 0)
        {
            y[node] = number;
            return;
        }
        else place(number, y[node]);
    }
}

void create_circuit(int M, vector<int> A)
{
    n = A.size();

    c.resize(M+1);
    x.resize(10*n);
    y.resize(10*n);

    state.resize(10*n);

    for(k=1; (1<<k) < n; ++k);

    e = (1<<k) - n;

    create_tree(1, (1<<k));

    int i;
    for(i=1; i<n; ++i)
        place(-A[i]);

    place(0);

    for(i=1; i<=nodes; ++i)
        x[i] = -x[i], y[i] = -y[i];

    c[0] = A[0];
    for(i=1; i<=M; ++i)
        c[i] = -1;

    x.erase(x.begin());
    y.erase(y.begin());

    while(x.size() > nodes) x.pop_back();
    while(y.size() > nodes) y.pop_back();

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:97:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |     while(x.size() > nodes) x.pop_back();
      |           ~~~~~~~~~^~~~~~~
doll.cpp:98:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     while(y.size() > nodes) y.pop_back();
      |           ~~~~~~~~~^~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 8188 KB Output is correct
3 Correct 60 ms 7812 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 77 ms 11724 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 8188 KB Output is correct
3 Correct 60 ms 7812 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 77 ms 11724 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 91 ms 14688 KB Output is correct
9 Correct 99 ms 14996 KB Output is correct
10 Correct 146 ms 22256 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 8188 KB Output is correct
3 Correct 60 ms 7812 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1356 KB Output is correct
6 Correct 77 ms 11724 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 91 ms 14688 KB Output is correct
9 Correct 99 ms 14996 KB Output is correct
10 Correct 146 ms 22256 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 161 ms 21908 KB Output is correct
15 Correct 97 ms 14260 KB Output is correct
16 Correct 142 ms 21812 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 144 ms 22140 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 81 ms 13740 KB Output is correct
3 Correct 83 ms 13764 KB Output is correct
4 Correct 139 ms 20808 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 81 ms 13740 KB Output is correct
3 Correct 83 ms 13764 KB Output is correct
4 Correct 139 ms 20808 KB Output is correct
5 Correct 152 ms 21556 KB Output is correct
6 Correct 130 ms 21460 KB Output is correct
7 Correct 131 ms 21512 KB Output is correct
8 Correct 138 ms 21140 KB Output is correct
9 Correct 90 ms 13792 KB Output is correct
10 Correct 129 ms 21104 KB Output is correct
11 Correct 190 ms 20808 KB Output is correct
12 Correct 86 ms 13724 KB Output is correct
13 Correct 109 ms 14104 KB Output is correct
14 Correct 96 ms 14096 KB Output is correct
15 Correct 97 ms 14288 KB Output is correct
16 Correct 3 ms 716 KB Output is correct
17 Correct 92 ms 13792 KB Output is correct
18 Correct 97 ms 13796 KB Output is correct
19 Correct 86 ms 13792 KB Output is correct
20 Correct 151 ms 21012 KB Output is correct
21 Correct 137 ms 20832 KB Output is correct
22 Correct 132 ms 20804 KB Output is correct