Submission #970455

#	Time	Username	Problem	Language	Result	Execution time	Memory
970455		jamesbamber	Mechanical Doll (IOI18_doll)	C++17	0 / 100	2 ms	348 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    int source = -N-1;
    vector<int> C(M + 1);
    for(int &x: C) x = source;


    int sz = 0;
    while((1<<sz) <= N) sz++;
    vector<int> X(N+sz), Y(N+sz);
    auto buildtree = [&](int len, int shift){
        vector<pair<int,int>> res(len-1);

        for(int i=0; i<len/2-1; i++) res[i] = {shift - (2*i+1), shift - (2*i+2)};
        for(int i=len/2-1; i<len-1; i++) res[i] = {M+1, M+1};

        for(auto [a, b]: res) cerr << a << " " << b << endl;
        return res;
    };

    int curr = -1;
    for(int i=0; i<sz; i++){
        Y[N+i] = -N-i-2;
        if((N & (1 << (sz-i-1))) == 0) X[N+i] = source;
        else{
            cerr << "AOSIFHSDFO" << " "  << i << endl;
            X[N+i] = curr;
            auto tree = buildtree((1<<(sz-i-1)), curr);
            for(auto [a, b]: tree) X[-curr-1] = a, Y[-curr-1] = b, curr--;
        }
    }
    Y[N+sz-1] = 0;

    vector<int> state(N+sz);
    function<void(int, int)> findnext = [&](int v, int id){
        int u = -v-1;
        cerr << v << " " << X[u] << " " << Y[u] << " " << state[u] << endl;
        assert(v < 0); 
        int next = state[u]?Y[u]:X[u];
        if(next == M+1){
            if(state[u]) Y[u] = id;
            else X[u] = id;
            state[u] ^= 1;
            return;
        }
        state[u] ^= 1;
        findnext(next, id);
    };

    for(int i=0; i<N; i++){
        findnext(source, A[i]);
        cerr << "SUS" << endl;
        for(int i=N; i<N+sz; i++) cerr << state[i];
        cerr << endl;
    }


    //assert(accumulate(state.begin(), state.end(), 0) == 0);


    for(int x: C) cerr << x << " "; cerr << endl;
    for(int x: X) cerr << x << " "; cerr << endl;
    for(int x: Y) cerr << x << " "; cerr << endl;


    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:65:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   65 |     for(int x: C) cerr << x << " "; cerr << endl;
      |     ^~~
doll.cpp:65:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |     for(int x: C) cerr << x << " "; cerr << endl;
      |                                     ^~~~
doll.cpp:66:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   66 |     for(int x: X) cerr << x << " "; cerr << endl;
      |     ^~~
doll.cpp:66:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   66 |     for(int x: X) cerr << x << " "; cerr << endl;
      |                                     ^~~~
doll.cpp:67:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   67 |     for(int x: Y) cerr << x << " "; cerr << endl;
      |     ^~~
doll.cpp:67:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   67 |     for(int x: Y) cerr << x << " "; cerr << endl;
      |                                     ^~~~

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