Submission #776040

#	Time	Username	Problem	Language	Result	Execution time	Memory
776040		phoenix	Mechanical Doll (IOI18_doll)	C++17	53 / 100	94 ms	19336 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]);
    }
}

void build1() {
    int k = 1;
    vector<int> order = {0}; 
    while(k < (int)A.size()) {
        if(k == 1) C[0] = 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)A.size() ? C[0] : A[order[2 * y] - k + (int)A.size() ]);
        Y[i] = (order[y * 2 + 1] < k - (int)A.size() ? C[0] : A[order[2 * y + 1] - k + (int)A.size() ]);
    }
}
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;
    int N = (int)A.size();
    if((N & N - 1) > 0) {
        for(int i = 0; i < N; i++) {
            g[A[i]].push_back(i);
        }
        C[0] = A[0];
        for(int i = 1; i <= M; i++) {
            build(i, g[i]);
        }
        answer(C, X, Y);
    } else {
        build1();
        for(int i = 1; i <= M; i++) C[i] = C[0];
        answer(C, X, Y);
    }
}
// int main() {
//     create_circuit(0, vector<int>());
// }

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:84:15: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   84 |     if((N & N - 1) > 0) {
      |             ~~^~~

• 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