oj.uz

Submission #767160

# Submission time Handle Problem Language Result Execution time Memory
767160 2023-06-26T12:56:32 Z adrilen Mechanical Doll (IOI18_doll) C++17
37 / 100
 112 ms 13644 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 - 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.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 1 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 54 ms 10812 KB Output is partially correct
3 Partially correct 57 ms 10800 KB Output is partially correct
4 Partially correct 65 ms 11348 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 54 ms 10812 KB Output is partially correct
3 Partially correct 57 ms 10800 KB Output is partially correct
4 Partially correct 65 ms 11348 KB Output is partially correct
5 Partially correct 112 ms 13644 KB Output is partially correct
6 Partially correct 94 ms 12584 KB Output is partially correct
7 Partially correct 104 ms 12912 KB Output is partially correct
8 Partially correct 84 ms 11964 KB Output is partially correct
9 Partially correct 54 ms 10812 KB Output is partially correct
10 Partially correct 74 ms 11772 KB Output is partially correct
11 Partially correct 73 ms 11316 KB Output is partially correct
12 Partially correct 65 ms 10856 KB Output is partially correct
13 Partially correct 71 ms 11628 KB Output is partially correct
14 Partially correct 74 ms 11848 KB Output is partially correct
15 Partially correct 77 ms 12344 KB Output is partially correct
16 Partially correct 2 ms 724 KB Output is partially correct
17 Correct 43 ms 7064 KB Output is correct
18 Partially correct 60 ms 10832 KB Output is partially correct
19 Partially correct 60 ms 10804 KB Output is partially correct
20 Partially correct 82 ms 11452 KB Output is partially correct
21 Partially correct 72 ms 11360 KB Output is partially correct
22 Partially correct 78 ms 11432 KB Output is partially correct