oj.uz

Submission #154774

# Submission time Handle Problem Language Result Execution time Memory
154774 2019-09-24T15:06:11 Z rama_pang Mechanical Doll (IOI18_doll) C++14
100 / 100
 191 ms 12896 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> state, L, R;
int id = 0, S = 0;

int build(int node, int triggers) {
    if (triggers == 0) return -1;
    if (node == 1) return id++;
    int now = - (++S);
    L[-now] = build(node / 2, triggers - min(node / 2, triggers));
    R[-now] = build(node / 2, min(node / 2, triggers));
    return now;
}

int dfs(int n) {
    if (n >= 0) return n;
    state[-n] ^= 1;
    if (state[-n] == 1) 
        return dfs(L[-n]);
    else 
        return dfs(R[-n]);
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int k = 1; while (k < A.size()) k *= 2;
    L.resize(k ), R.resize(k), state.resize(k);
    build(k, A.size());
    vector<int> C(M + 1, -1), dest(id + id), X(S), Y(S);
    for (int i = 0; i < A.size(); i++) dest[dfs(-1)] = A[i];
    for (int i = 1; i <= S; i++) {
        X[i - 1] = L[i], Y[i - 1] = R[i];
        if (0 <= X[i - 1]) X[i - 1] = dest[X[i - 1]];
        if (0 <= Y[i - 1]) Y[i - 1] = dest[Y[i - 1]];
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:28:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     int k = 1; while (k < A.size()) k *= 2;
      |                       ~~^~~~~~~~~~
doll.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < A.size(); i++) dest[dfs(-1)] = A[i];
      |                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 53 ms 5584 KB Output is correct
3 Correct 50 ms 5400 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 75 ms 7256 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 53 ms 5584 KB Output is correct
3 Correct 50 ms 5400 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 75 ms 7256 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 9524 KB Output is correct
9 Correct 102 ms 10044 KB Output is correct
10 Correct 191 ms 12896 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 53 ms 5584 KB Output is correct
3 Correct 50 ms 5400 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 1356 KB Output is correct
6 Correct 75 ms 7256 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 101 ms 9524 KB Output is correct
9 Correct 102 ms 10044 KB Output is correct
10 Correct 191 ms 12896 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 163 ms 12408 KB Output is correct
15 Correct 90 ms 9012 KB Output is correct
16 Correct 148 ms 12188 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 152 ms 12664 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 300 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 88 ms 8508 KB Output is correct
3 Correct 88 ms 8508 KB Output is correct
4 Correct 142 ms 11156 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 88 ms 8508 KB Output is correct
3 Correct 88 ms 8508 KB Output is correct
4 Correct 142 ms 11156 KB Output is correct
5 Correct 161 ms 12160 KB Output is correct
6 Correct 140 ms 11736 KB Output is correct
7 Correct 134 ms 11848 KB Output is correct
8 Correct 165 ms 11420 KB Output is correct
9 Correct 96 ms 8512 KB Output is correct
10 Correct 135 ms 11340 KB Output is correct
11 Correct 132 ms 11156 KB Output is correct
12 Correct 134 ms 8512 KB Output is correct
13 Correct 93 ms 8816 KB Output is correct
14 Correct 88 ms 8856 KB Output is correct
15 Correct 94 ms 8984 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 79 ms 6960 KB Output is correct
18 Correct 90 ms 8516 KB Output is correct
19 Correct 90 ms 8484 KB Output is correct
20 Correct 146 ms 11240 KB Output is correct
21 Correct 144 ms 11152 KB Output is correct
22 Correct 171 ms 11156 KB Output is correct