Submission #612280

#	Time	Username	Problem	Language	Result	Execution time	Memory
612280		Jomnoi	Mechanical Doll (IOI18_doll)	C++17	15 / 100	201 ms	40856 KiB

doll

#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;
set <int> keepnxt[MAX_M];
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++) {
        if(keepnxt[A[i]].count(A[i + 1])) {
            continue;
        }
        if(A[i] != A[i + 1]) {
            keepnxt[A[i]].insert(A[i + 1]);
        }
        
        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()) {
                    if(i < (1<<numberofLevel) - 1) {
                        Y[leaf[i / 2]] = -root;
                    }
                    else {
                        Y[leaf[i / 2]] = nxt[a].back();
                    }
                }
                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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 0 / 56