oj.uz

Submission #767154

# Submission time Handle Problem Language Result Execution time Memory
767154 2023-06-26T12:49:52 Z adrilen Mechanical Doll (IOI18_doll) C++17
9 / 100
 121 ms 13632 KB 
#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); // 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 << "\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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 62 ms 10828 KB Output is partially correct
3 Partially correct 58 ms 10816 KB Output is partially correct
4 Partially correct 78 ms 11340 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 62 ms 10828 KB Output is partially correct
3 Partially correct 58 ms 10816 KB Output is partially correct
4 Partially correct 78 ms 11340 KB Output is partially correct
5 Partially correct 121 ms 13632 KB Output is partially correct
6 Partially correct 105 ms 12644 KB Output is partially correct
7 Partially correct 96 ms 12916 KB Output is partially correct
8 Partially correct 86 ms 11952 KB Output is partially correct
9 Partially correct 61 ms 10816 KB Output is partially correct
10 Partially correct 75 ms 11708 KB Output is partially correct
11 Partially correct 73 ms 11384 KB Output is partially correct
12 Partially correct 80 ms 10852 KB Output is partially correct
13 Partially correct 77 ms 11600 KB Output is partially correct
14 Partially correct 77 ms 11904 KB Output is partially correct
15 Partially correct 94 ms 12364 KB Output is partially correct
16 Partially correct 3 ms 724 KB Output is partially correct
17 Incorrect 61 ms 10872 KB Output isn't correct
18 Halted 0 ms 0 KB -