oj.uz

Submission #612201

# Submission time Handle Problem Language Result Execution time Memory
612201 2022-07-29T11:30:56 Z Jomnoi Mechanical Doll (IOI18_doll) C++17
15 / 100
 91 ms 25728 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

const int MAX_M = 1e5 + 5;
const int INF = 1e9 + 7;

int N, M, S;
vector <int> nxt[MAX_M];
vector<int> C, X, Y;
vector <int> leaf;
vector <int> pattern[20];

void build(int u, int d) {
    if(d == 0) {
        return;
    }

    X[u - 1] = -(++S);
    if(d == 1) {
        leaf.push_back(S - 1);
    }
    build(S, d - 1);

    Y[u - 1] = -(++S);
    if(d == 1) {
        leaf.push_back(S - 1);
    }
    build(S, d - 1);
}

void create_circuit(int m, vector <int> A) {
    N = A.size(), M = m;
    C.resize(M + 1);
    X.resize(1e6, INF);
    Y.resize(1e6, INF);

    pattern[0].push_back(0);
    for(int j = 1; j < 20; j++) {
        pattern[j].resize(pattern[j - 1].size() * 2);
        for(int i = 0; i < pattern[j - 1].size(); i++) {
            pattern[j][i * 2] = pattern[j - 1][i];
        }
        for(int i = 0; i < pattern[j].size(); i += 2) {
            pattern[j][i + 1] = pattern[j][i] + (1<<(j - 1));
        }
    }

    A.push_back(0);
    for(int i = 0; i < N; i++) {
        nxt[A[i]].push_back(A[i + 1]);
    }

    C[0] = A[0];
    for(int a = 1; a <= M; a++) {
        if(nxt[a].empty()) {
            continue;
        }
        else if(nxt[a].size() == 1) {
            C[a] = nxt[a][0];
        }
        else {
            leaf.clear();
            int root = ++S;
            C[a] = -S;
            
            int numberofLevel = ceil(1.0 * log2(nxt[a].size()));
            build(S, numberofLevel - 1);
            if(numberofLevel == 1) {
                leaf.push_back(root - 1);
            }

            for(int i = 0; i < (1<<numberofLevel); i += 2) {
                int idx = pattern[numberofLevel][i];
                if(idx + 1 >= nxt[a].size()) {
                    X[leaf[i / 2]] = -root;
                }
                else {
                    X[leaf[i / 2]] = nxt[a][idx];
                }
            }
            for(int i = 1; i < (1<<numberofLevel); i += 2) {
                int idx = pattern[numberofLevel][i];
                if(idx + 1 >= nxt[a].size() and i != (1<<numberofLevel) - 1) {
                    Y[leaf[i / 2]] = -root;
                }
                else {
                    Y[leaf[i / 2]] = nxt[a][idx];
                }
            }
        }
    }

    while(X.back() == INF) {
        X.pop_back();
    }
    while(Y.back() == INF) {
        Y.pop_back();
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0; i < pattern[j - 1].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < pattern[j].size(); i += 2) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
doll.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 if(idx + 1 >= nxt[a].size()) {
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 if(idx + 1 >= nxt[a].size() and i != (1<<numberofLevel) - 1) {
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14544 KB Output is correct
2 Correct 31 ms 18796 KB Output is correct
3 Correct 30 ms 18444 KB Output is correct
4 Correct 9 ms 14556 KB Output is correct
5 Correct 19 ms 15700 KB Output is correct
6 Correct 38 ms 20580 KB Output is correct
7 Correct 10 ms 14556 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14544 KB Output is correct
2 Correct 31 ms 18796 KB Output is correct
3 Correct 30 ms 18444 KB Output is correct
4 Correct 9 ms 14556 KB Output is correct
5 Correct 19 ms 15700 KB Output is correct
6 Correct 38 ms 20580 KB Output is correct
7 Correct 10 ms 14556 KB Output is correct
8 Correct 55 ms 21100 KB Output is correct
9 Correct 56 ms 21708 KB Output is correct
10 Correct 80 ms 24496 KB Output is correct
11 Correct 9 ms 14548 KB Output is correct
12 Correct 11 ms 14676 KB Output is correct
13 Correct 11 ms 14604 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14544 KB Output is correct
2 Correct 31 ms 18796 KB Output is correct
3 Correct 30 ms 18444 KB Output is correct
4 Correct 9 ms 14556 KB Output is correct
5 Correct 19 ms 15700 KB Output is correct
6 Correct 38 ms 20580 KB Output is correct
7 Correct 10 ms 14556 KB Output is correct
8 Correct 55 ms 21100 KB Output is correct
9 Correct 56 ms 21708 KB Output is correct
10 Correct 80 ms 24496 KB Output is correct
11 Correct 9 ms 14548 KB Output is correct
12 Correct 11 ms 14676 KB Output is correct
13 Correct 11 ms 14604 KB Output is correct
14 Incorrect 81 ms 25728 KB wrong motion
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14548 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 14624 KB Output is partially correct
2 Correct 46 ms 20280 KB Output is correct
3 Partially correct 66 ms 22232 KB Output is partially correct
4 Partially correct 78 ms 23440 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 14624 KB Output is partially correct
2 Correct 46 ms 20280 KB Output is correct
3 Partially correct 66 ms 22232 KB Output is partially correct
4 Partially correct 78 ms 23440 KB Output is partially correct
5 Incorrect 91 ms 25724 KB wrong motion
6 Halted 0 ms 0 KB -