oj.uz

Submission #197268

# Submission time Handle Problem Language Result Execution time Memory
197268 2020-01-19T19:41:02 Z stefdasca Mechanical Doll (IOI18_doll) C++14
100 / 100
 145 ms 11876 KB 
#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

int adja[400002], adjb[400002], sw = 1, tot, state[400002];

void build(int p, int st, int dr)
{
    int mid = (st + dr) / 2;
    if(st + 1 == dr)
    {
        if(tot <= mid)
            adja[p] = 1;
        return;
    }
    ++sw;
    adjb[p] = sw;
    build(sw, st, mid);
    if(tot > mid)
    {
        ++sw;
        adja[p] = sw;
        build(sw, mid+1, dr);
    }
    else
        adja[p] = 1;
}

void dfs(int nod, int val)
{
    state[nod] ^= 1;
    if(!state[nod])
    {
        if(adjb[nod])
            dfs(adjb[nod], val);
        else
            adjb[nod] = val;
    }
    else
    {
        if(adja[nod])
            dfs(adja[nod], val);
        else
            adja[nod] = val;
    }
}
void create_circuit(int M, vector<int> A)
{
    vector<int> C;
    C.push_back(A[0]);
    for(int i = 1; i <= M; ++i)
        C.push_back(-1);
    A.push_back(0);
    int sz = 1;
    while(sz * 2 <= (int) A.size() - 2)
        sz *= 2;
    sz *= 2;
    tot = A.size() - 1;
    build(1, 1, sz);
    for(int i = 1; i < A.size(); ++i)
        dfs(1, -A[i]);
    vector<int> X(sw), Y(sw);
    for(int k = 0; k < sw; ++k)
    {
        X[k] = -adja[k + 1];
        Y[k] = -adjb[k + 1];
    }
    answer(C, X, Y);
    /*
    for(int i = 0; i < C.size(); ++i)
        cout << C[i] << " ";
    cout << '\n';
    for(int i = 0; i < sw; ++i)
        cout << X[i] << " " << Y[i] << '\n';
    */
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 1; i < A.size(); ++i)
      |                    ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 44 ms 4408 KB Output is correct
3 Correct 44 ms 4380 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1604 KB Output is correct
6 Correct 70 ms 6496 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 44 ms 4408 KB Output is correct
3 Correct 44 ms 4380 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1604 KB Output is correct
6 Correct 70 ms 6496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 7764 KB Output is correct
9 Correct 87 ms 8188 KB Output is correct
10 Correct 136 ms 11876 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 44 ms 4408 KB Output is correct
3 Correct 44 ms 4380 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1604 KB Output is correct
6 Correct 70 ms 6496 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 7764 KB Output is correct
9 Correct 87 ms 8188 KB Output is correct
10 Correct 136 ms 11876 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 133 ms 11484 KB Output is correct
15 Correct 91 ms 7452 KB Output is correct
16 Correct 127 ms 11244 KB Output is correct
17 Correct 1 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 142 ms 11624 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 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 1 ms 204 KB Output is correct
3 Correct 1 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 1 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 72 ms 6596 KB Output is correct
3 Correct 83 ms 6588 KB Output is correct
4 Correct 141 ms 9960 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 72 ms 6596 KB Output is correct
3 Correct 83 ms 6588 KB Output is correct
4 Correct 141 ms 9960 KB Output is correct
5 Correct 121 ms 11116 KB Output is correct
6 Correct 120 ms 10856 KB Output is correct
7 Correct 123 ms 10928 KB Output is correct
8 Correct 124 ms 10776 KB Output is correct
9 Correct 79 ms 6576 KB Output is correct
10 Correct 119 ms 10620 KB Output is correct
11 Correct 115 ms 10292 KB Output is correct
12 Correct 75 ms 6820 KB Output is correct
13 Correct 76 ms 7212 KB Output is correct
14 Correct 78 ms 7300 KB Output is correct
15 Correct 82 ms 7356 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 72 ms 6844 KB Output is correct
18 Correct 74 ms 6720 KB Output is correct
19 Correct 75 ms 6816 KB Output is correct
20 Correct 122 ms 10524 KB Output is correct
21 Correct 128 ms 10248 KB Output is correct
22 Correct 145 ms 10392 KB Output is correct