oj.uz

Submission #928519

# Submission time Handle Problem Language Result Execution time Memory
928519 2024-02-16T14:25:01 Z GrindMachine Mechanical Doll (IOI18_doll) C++17
100 / 100
 100 ms 9444 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

design idea:
build a chain of length = k, k is the smallest num s.t 2^k >= n
each of them are connected to each other by Y edges
if the root is visited x times, then:
1st subtree visited x/2 times,
2nd subtree visited x/4 times,
3rd subtree visited x/8 times,
...

decompose n into pows of 2
for each pow of 2, build a binary tree in the corresponding position on the chain
eg: a binary tree of size 2^(k-1) goes on the first position in the chain, size 2^(k-2) goes on the 2nd position etc

there are exactly n binary tree nodes in total
each node corresponds to the state after visiting the first i triggers
the state for each node can be found by simulating the ball from the root
if cnt no.of vals have been visited before reaching a leaf node (including the current node), then the current node is a[cnt-1], so it has to be connected to a[cnt]
if cnt == n, then it means that this node is the last node
so connect it to the root of the chain (after this, no leaf node is every encountered, and the ball leaves the Y exit of the last node on the chain to reach 0)
when the ball leaves by the Y exit of the last node on the chain, all switches would have state X
we also use <= n+log2(n) nodes (~n for the bin.tree, ~log2(n) for the chain)
so the construction is valid

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "doll.h"

void create_circuit(int m, std::vector<int> a) {
    // int N = A.size();
    // std::vector<int> C(M + 1);
    // C[0] = -1;
    // for (int i = 1; i <= M; ++i) {
    //     C[i] = 1;
    // }
    // std::vector<int> X(N), Y(N);
    // for (int k = 0; k < N; ++k) {
    //     X[k] = Y[k] = A[k];
    // }
    // answer(C, X, Y);

    int n = sz(a);
    a.pb(0);
    vector<int> b(m+1);
    b[0] = a[0];

    vector<int> sx(1), sy(1), leaf(1), flipped(1);

    int siz = 1;
    while(siz <= n) siz <<= 1;
    int chain_siz = __lg(siz);

    int root = 1;

    rep1(i,m){
        b[i] = -root;
    }
    b[0] = a[0];

    rep1(i,chain_siz){
        sx.pb(0), sy.pb(0);
    }
    rep1(i,chain_siz-1){
        sx[root-1+i] = -root;
        sy[root-1+i] = -(root+i);
    }

    sx[root-1+chain_siz] = -root;
    sy[root-1+chain_siz] = 0;

    rev(bit,chain_siz-1,0){
        if(!(n&(1<<bit))) conts;
        if(!bit){
            while(sz(leaf) < sz(sx)){
                leaf.pb(0);
            }
            leaf[root-1+chain_siz] = 1;
            conts;
        }

        // build bin tree, depth = bit-1
        int pos_on_chain = root-1+chain_siz-bit;
        int ptr = sz(sx);
        sx.pb(-root), sy.pb(-root);
        sx[pos_on_chain] = -ptr;
        queue<pii> q;
        q.push({ptr,0});

        while(!q.empty()){
            auto [u,d] = q.front();
            q.pop();

            if(d >= bit-1){
                while(sz(leaf) < sz(sx)){
                    leaf.pb(0);
                }
                leaf[u] = 1;
                conts;
            }

            sx[u] = -sz(sx);
            sy[u] = -(sz(sx)+1);

            sx.pb(-root), sy.pb(-root);
            sx.pb(-root), sy.pb(-root);

            q.push({-sx[u],d+1});
            q.push({-sy[u],d+1});
        }
    }

    while(sz(flipped) < sz(sx)){
        flipped.pb(0);
    }

    int ptr = root;
    int cnt = 0;

    while(true){
        if(leaf[ptr]){
            cnt++;
            if(cnt == n) break;

            flipped[ptr] ^= 1;
            int nxt = a[cnt];

            if(flipped[ptr]){
                sx[ptr] = nxt;
            }
            else{
                sy[ptr] = nxt;
            }

            ptr = root;
        }
        else{
            flipped[ptr] ^= 1;
            if(flipped[ptr]){
                ptr = -sx[ptr];
            }
            else{
                ptr = -sy[ptr];
            }
        }
    }

    sx.erase(sx.begin());
    sy.erase(sy.begin());
    int mx_allowed = n+__lg(n-1)+1;
    assert(sz(sx) <= mx_allowed);
    answer(b,sx,sy);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 32 ms 3816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 48 ms 5440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 32 ms 3816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 48 ms 5440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 62 ms 6532 KB Output is correct
9 Correct 67 ms 6784 KB Output is correct
10 Correct 93 ms 9444 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 34 ms 4216 KB Output is correct
3 Correct 32 ms 3816 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 48 ms 5440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 62 ms 6532 KB Output is correct
9 Correct 67 ms 6784 KB Output is correct
10 Correct 93 ms 9444 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 96 ms 9044 KB Output is correct
15 Correct 59 ms 6004 KB Output is correct
16 Correct 90 ms 8936 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 600 KB Output is correct
20 Correct 89 ms 9352 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 56 ms 5756 KB Output is correct
3 Correct 55 ms 5764 KB Output is correct
4 Correct 96 ms 8164 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 56 ms 5756 KB Output is correct
3 Correct 55 ms 5764 KB Output is correct
4 Correct 96 ms 8164 KB Output is correct
5 Correct 88 ms 8680 KB Output is correct
6 Correct 86 ms 8616 KB Output is correct
7 Correct 100 ms 8868 KB Output is correct
8 Correct 85 ms 8312 KB Output is correct
9 Correct 62 ms 5748 KB Output is correct
10 Correct 84 ms 8424 KB Output is correct
11 Correct 82 ms 8164 KB Output is correct
12 Correct 60 ms 6012 KB Output is correct
13 Correct 57 ms 5800 KB Output is correct
14 Correct 57 ms 5948 KB Output is correct
15 Correct 59 ms 6004 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 54 ms 6832 KB Output is correct
18 Correct 56 ms 5756 KB Output is correct
19 Correct 55 ms 5756 KB Output is correct
20 Correct 86 ms 8412 KB Output is correct
21 Correct 83 ms 8164 KB Output is correct
22 Correct 86 ms 8172 KB Output is correct