oj.uz

Submission #767143

# Submission time Handle Problem Language Result Execution time Memory
767143 2023-06-26T12:32:12 Z adrilen Mechanical Doll (IOI18_doll) C++17
9 / 100
 67 ms 14120 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 wrong serial number
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB wrong serial number
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 232 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 56 ms 10812 KB Output is partially correct
3 Partially correct 58 ms 10828 KB Output is partially correct
4 Partially correct 65 ms 11312 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 56 ms 10812 KB Output is partially correct
3 Partially correct 58 ms 10828 KB Output is partially correct
4 Partially correct 65 ms 11312 KB Output is partially correct
5 Runtime error 67 ms 14120 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -