Submission #767160

#	Time	Username	Problem	Language	Result	Execution time	Memory
767160		adrilen	Mechanical Doll (IOI18_doll)	C++17	37 / 100	112 ms	13644 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int max_siz = 1 << 18;


constexpr int root = 1;
int l[max_siz] = { 0 }, r[max_siz] = { 0 };

int timing(int p, int bit)
{
    int output = 0;
    for (int i = bit; i >= 0; i--)
    {
        if (p & (1 << i)) output += (1 << (bit - i));
    }
    return output;
}



// n is the length of a
// m is the number of triggers

bool can_be_reached[max_siz] = { 0 };
int prefix_sum[max_siz] = { 0 };


void reach_test(int p)
{
    can_be_reached[p] = true;

    if (l[p] > root) reach_test(p * 2);
    if (r[p] > root) reach_test(p * 2 + 1);
}

void create_circuit(int m, std::vector<int> a) { // Legg 0 til på andre switch i treet
    if (a.size() == 1)
    {
        answer({1, 0}, {}, {});
        return ;
    }
    
    a.emplace_back(0);

    int n = a.size();


    map<int, int> ma;
    int next_int = 0;
    for (int i : a)
    {
        if (ma.count(i) == 0) ma[i] = next_int++;
    }

    int bit = 31 - __builtin_clz(n - 1); // N / 2
    int siz = (1 << bit);  

    for (int i = 0; i < 2 * siz; i++) l[i] = r[i] = root;


    for (int i = 1; i < siz; i++) l[i] = i * 2, r[i] = i * 2 + 1;
    // cout << "bit: " << bit << ", siz: " << siz << "\n";
    // for (int i = 0; i < n; i++) cout << timing(i, bit) << "\n";


    next_int = 0;
    int o;
    for (int i = 0; i < n - 1; i++)
    {
        o = timing(i, bit);
        
        if (o & 1) r[siz + o/2] = -a[i];
        else l[siz + o / 2] = -a[i];
    }

    r[siz * 2 - 1] = 0;


    // for (int i = 1; i < 2 * siz; i++)
    // {
    //     if (__builtin_popcount(i) == 1) cout << "\n";
    //     cout << i << " " <<  l[i] << " " << r[i] << "\n";
    // }

    r[siz * 2 - 1] = 0;


    for (int level = 0; level < bit; level++)
    {
        for (int i = (1 << (bit - level + 1)) - 1; i >= (1 << (bit - level)); i--)
        {
            if (l[i] == root && r[i] == root) {
                if (i & 1) {
                    r[i / 2] = root;
                } else {
                    l[i / 2] = root;
                }
            }
            // cout << i << " ";
        }
        // cout << "\n";
    }


    // for (int i = 1; i < 2 * siz; i++)
    // {
    //     if (__builtin_popcount(i) == 1) cout << "\n";
    //     cout << i << " " <<  l[i] << " " << r[i] << "\n";
    // }


    reach_test(root);
    
    for (int i = 1; i < siz * 2; i++) prefix_sum[i] = prefix_sum[i - 1] + !can_be_reached[i];
    // for (int i = 1; i < siz * 2; i++) cout << prefix_sum[i] << " ";
    // cout << "\n";

    // for (int i = siz * 2 - 1; i >= 0; i--)
    // {
    //     l[i] = l[i + prefix_sum[i]] - prefix_sum[l[i + prefix_sum[i]]];
    //     r[i] = r[i + prefix_sum[i]] - prefix_sum[r[i + prefix_sum[i]]];
    // }

    

    vector <int> c(m + 1, -root);
    vector <int> x(siz * 2 - 1 - prefix_sum[siz * 2 - 1]);
    vector <int> y(x.size());
    for (size_t i = 0; i < x.size(); i++) x[i] = -l[i + 1];
    for (size_t i = 0; i < y.size(); i++) y[i] = -r[i + 1];

    // cout << "S: " << x.size() << " M: " << m << "\n";
    // for (int i : x) cout << i << " ";
    // cout << "\n";
    // for (int i : y) cout << i << " ";
    // cout << "\n";

    answer(c, x, y);
}

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