Submission #776050

#	Time	Username	Problem	Language	Result	Execution time	Memory
776050		phoenix	Mechanical Doll (IOI18_doll)	C++17	53 / 100	113 ms	19320 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"

using namespace std;

vector<int> A, C, X, Y;
int S = 0;

int create_switch() {
    X.push_back(-1);
    Y.push_back(-1);
    S++;
    return -S;    
}

void build(int trigger, vector<int> in) {
    if((int)in.empty()) {
        C[trigger] = 0;
        return;
    }
    if((int)in.size() == 1) {
        C[trigger] = A[in[0] + 1];
        return;
    }
    int k = 1;
    vector<int> order = {0}; 
    while(k < (int)in.size()) {
        if(k == 1) C[trigger] = create_switch();
        else {
            int len = S;
            for(int i = len - k / 2; i < len; i++) {
                X[i] = create_switch();
                Y[i] = create_switch();
            }
        }
        vector<int> new_ord;
        for(int i = 0; i < k; i++) 
            new_ord.push_back(order[i]),
            new_ord.push_back(order[i] + k);
        order = new_ord;
        k *= 2;
    }
    for(int i = S - k / 2; i < S; i++) {
        int y = i - S + k / 2;
        X[i] = (order[y * 2] < k - (int)in.size() ? C[trigger] : A[in[ order[2 * y] - k + (int)in.size() ] + 1]);
        Y[i] = (order[y * 2 + 1] < k - (int)in.size() ? C[trigger] : A[in[ order[2 * y + 1] - k + (int)in.size() ] + 1]);
    }
}
const int N = 1e5 + 10;
vector<int> g[N];

void create_circuit(int M, std::vector<int> a) {
    C.resize(M + 1);
    a.push_back(0);
    A = a;
    for(int i = 0; i < (int)A.size(); i++) {
        g[A[i]].push_back(i);
    }
    C[0] = A[0];
    for(int i = 1; i <= M; i++) {
        build(i, g[i]);
    }
    if(S > 2 * (int)a.size()) {
        1 / 0;
        return;
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:64:11: warning: division by zero [-Wdiv-by-zero]
   64 |         1 / 0;
      |         ~~^~~
doll.cpp:64:11: warning: statement has no effect [-Wunused-value]

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