oj.uz

Submission #767145

# Submission time Handle Problem Language Result Execution time Memory
767145 2023-06-26T12:33:53 Z adrilen Mechanical Doll (IOI18_doll) C++17
9 / 100
 104 ms 13700 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
    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 0 ms 212 KB Output is partially correct
2 Partially correct 57 ms 10816 KB Output is partially correct
3 Partially correct 68 ms 10832 KB Output is partially correct
4 Partially correct 62 ms 11356 KB Output is partially correct

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 57 ms 10816 KB Output is partially correct
3 Partially correct 68 ms 10832 KB Output is partially correct
4 Partially correct 62 ms 11356 KB Output is partially correct
5 Partially correct 104 ms 13700 KB Output is partially correct
6 Partially correct 97 ms 12692 KB Output is partially correct
7 Partially correct 96 ms 12924 KB Output is partially correct
8 Partially correct 91 ms 12044 KB Output is partially correct
9 Partially correct 60 ms 10824 KB Output is partially correct
10 Partially correct 75 ms 11696 KB Output is partially correct
11 Partially correct 73 ms 11324 KB Output is partially correct
12 Partially correct 61 ms 10832 KB Output is partially correct
13 Partially correct 72 ms 11592 KB Output is partially correct
14 Partially correct 89 ms 11832 KB Output is partially correct
15 Partially correct 79 ms 12276 KB Output is partially correct
16 Partially correct 2 ms 724 KB Output is partially correct
17 Incorrect 63 ms 10832 KB Output isn't correct
18 Halted 0 ms 0 KB -