oj.uz

Submission #928515

# Submission time Handle Problem Language Result Execution time Memory
928515 2024-02-16T14:13:23 Z GrindMachine Mechanical Doll (IOI18_doll) C++17
100 / 100
 98 ms 10872 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

/*



*/

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 last_guy = inf1, last_type = inf1;

    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 = 0;
            if(cnt < n) nxt = a[cnt];
            else{
                // last_guy = ptr;
                // last_type = flipped[ptr];
            }

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

            ptr = root;

            // if(cnt == n) break;
        }
        else{
            flipped[ptr] ^= 1;
            if(flipped[ptr]){
                ptr = -sx[ptr];
            }
            else{
                ptr = -sy[ptr];
            }
        }
    }

    vector<pii> pending;
    rep1(i,m){
        // if(!pos[i].empty() and sz(pos[i]) != 2){
        //     pending.pb({b[i],leave[i]});
        // }
    }

    // rep(i,sz(pending)-1){
    //     sy[-pending[i].ss] = pending[i+1].ff;
    // }

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

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
doll.cpp:203:5: note: in expansion of macro 'debug'
  203 |     debug(mx_allowed);
      |     ^~~~~
doll.cpp:201:9: warning: unused variable 'mx_allowed' [-Wunused-variable]
  201 |     int mx_allowed = n+__lg(n-1)+1;
      |         ^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 34 ms 4660 KB Output is correct
3 Correct 31 ms 4396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 48 ms 6096 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 34 ms 4660 KB Output is correct
3 Correct 31 ms 4396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 48 ms 6096 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 61 ms 7540 KB Output is correct
9 Correct 64 ms 7800 KB Output is correct
10 Correct 95 ms 10872 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 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 348 KB Output is correct
2 Correct 34 ms 4660 KB Output is correct
3 Correct 31 ms 4396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1372 KB Output is correct
6 Correct 48 ms 6096 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 61 ms 7540 KB Output is correct
9 Correct 64 ms 7800 KB Output is correct
10 Correct 95 ms 10872 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 93 ms 10492 KB Output is correct
15 Correct 59 ms 7032 KB Output is correct
16 Correct 98 ms 10420 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 93 ms 10800 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 0 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 56 ms 6784 KB Output is correct
3 Correct 56 ms 6772 KB Output is correct
4 Correct 87 ms 9712 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 56 ms 6784 KB Output is correct
3 Correct 56 ms 6772 KB Output is correct
4 Correct 87 ms 9712 KB Output is correct
5 Correct 88 ms 10220 KB Output is correct
6 Correct 92 ms 9928 KB Output is correct
7 Correct 88 ms 9964 KB Output is correct
8 Correct 88 ms 9704 KB Output is correct
9 Correct 55 ms 6776 KB Output is correct
10 Correct 86 ms 9740 KB Output is correct
11 Correct 85 ms 9708 KB Output is correct
12 Correct 56 ms 6796 KB Output is correct
13 Correct 59 ms 6780 KB Output is correct
14 Correct 65 ms 6864 KB Output is correct
15 Correct 58 ms 6776 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 48 ms 7788 KB Output is correct
18 Correct 56 ms 6792 KB Output is correct
19 Correct 57 ms 6776 KB Output is correct
20 Correct 96 ms 9672 KB Output is correct
21 Correct 85 ms 9720 KB Output is correct
22 Correct 91 ms 9740 KB Output is correct