oj.uz

Submission #970458

# Submission time Handle Problem Language Result Execution time Memory
970458 2024-04-26T14:49:37 Z jamesbamber Mechanical Doll (IOI18_doll) C++17
64.611 / 100
 94 ms 9324 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{
            if(sz-i-1 == 0){
                X[N+i] = M+1;
            }
            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 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
15.7161781332 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Partially correct 60 ms 5580 KB Output is partially correct
3 Partially correct 60 ms 5712 KB Output is partially correct
4 Partially correct 93 ms 8524 KB Output is partially correct

Subtask #6
48.8947764144 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Output is partially correct
2 Partially correct 60 ms 5580 KB Output is partially correct
3 Partially correct 60 ms 5712 KB Output is partially correct
4 Partially correct 93 ms 8524 KB Output is partially correct
5 Partially correct 93 ms 9324 KB Output is partially correct
6 Partially correct 90 ms 8980 KB Output is partially correct
7 Partially correct 94 ms 9264 KB Output is partially correct
8 Partially correct 90 ms 8636 KB Output is partially correct
9 Partially correct 56 ms 5708 KB Output is partially correct
10 Partially correct 89 ms 8728 KB Output is partially correct
11 Partially correct 88 ms 8444 KB Output is partially correct
12 Partially correct 60 ms 5720 KB Output is partially correct
13 Partially correct 64 ms 6212 KB Output is partially correct
14 Partially correct 60 ms 6280 KB Output is partially correct
15 Partially correct 60 ms 6460 KB Output is partially correct
16 Partially correct 2 ms 604 KB Output is partially correct
17 Partially correct 55 ms 5712 KB Output is partially correct
18 Partially correct 63 ms 5712 KB Output is partially correct
19 Partially correct 58 ms 5712 KB Output is partially correct
20 Partially correct 87 ms 8472 KB Output is partially correct
21 Partially correct 90 ms 8448 KB Output is partially correct
22 Partially correct 87 ms 8272 KB Output is partially correct