oj.uz

Submission #970456

# Submission time Handle Problem Language Result Execution time Memory
970456 2024-04-26T14:45:05 Z jamesbamber Mechanical Doll (IOI18_doll) C++17
0 / 100
 1 ms 600 KB 
#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};

        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{
            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;
        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]);
    }


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

    answer(C, X, Y);
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -