oj.uz

Submission #926961

# Submission time Handle Problem Language Result Execution time Memory
926961 2024-02-14T05:52:52 Z GrindMachine Mechanical Doll (IOI18_doll) C++17
53 / 100
 120 ms 14956 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);
    vector<int> b(m+1);

    vector<int> pos[m+1];
    rep(i,n) pos[a[i]].pb(i);
    
    vector<int> root(m+1);
    vector<int> sx(1), sy(1), flipped;
    int switch_ptr = 1;

    rep1(i,m){
        if(sz(pos[i]) <= 1) conts;
        root[i] = -switch_ptr;
        sx.pb(0), sy.pb(0);
        switch_ptr++;
    }

    b[0] = a[0];
    rep(i,n){
        b[a[i]] = root[a[i]];
    }

    ll last_guy = inf2, last_type = inf2;
    vector<pll> pending;

    rep1(x,m){
        if(pos[x].empty()) conts;
        auto &p = pos[x];
        int c = sz(p);
        if(c == 1){
            ll i = p[0];
            if(i+1 < n){
                b[x] = a[i+1];
            }
            else{
                last_guy = x;
            }

            conts;
        }

        int siz = 1;
        while(siz < c) siz <<= 1;

        queue<pll> q;
        q.push({root[x],0});
        ll depth = __lg(siz)-1;

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

            sx[-u] = -switch_ptr;
            sx.pb(0), sy.pb(0);
            switch_ptr++;

            sy[-u] = -switch_ptr;
            sx.pb(0), sy.pb(0);
            switch_ptr++;

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

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

        rep1(iter,siz){
            int ptr = root[x];
            rep1(d,depth){
                flipped[-ptr] ^= 1;
                if(flipped[-ptr]){
                    ptr = sx[-ptr];
                }
                else{
                    ptr = sy[-ptr];
                }
            }

            if(iter <= c){
                ll i = p[iter-1];
                if(i+1 < n){
                    ll nxt = a[i+1];
                    flipped[-ptr] ^= 1;
                    if(flipped[-ptr]){
                        sx[-ptr] = nxt;
                    }
                    else{
                        sy[-ptr] = nxt;
                    }
                }
                else{
                    last_guy = ptr;
                    flipped[-ptr] ^= 1;
                    if(flipped[-ptr]){
                        last_type = 0;
                    }
                    else{
                        last_type = 1;
                    }
                }
            }
            else{
                ll nxt = 0;
                if(iter < siz){
                    nxt = root[x];
                    flipped[-ptr] ^= 1;
                    if(flipped[-ptr]){
                        sx[-ptr] = nxt;
                    }
                    else{
                        sy[-ptr] = nxt;
                    }
                }
                else{
                    flipped[-ptr] ^= 1;
                    pending.pb({root[x],ptr});
                }
            }
        }

        // rep1(iter,siz){
        //     ll ptr = 1;
        //     while(ptr < siz/2){
        //         flipped[ptr] ^= 1;
        //         if(flipped[ptr]){
        //             ptr = ptr*2;
        //         }
        //         else{
        //             ptr = ptr*2+1;
        //         }
        //     }

        //     ll nxt = 0;

        //     if(iter < c){
        //         nxt = 1;
        //     }
        //     else if(iter < siz){
        //         nxt = -1;
        //     }
        //     else{
        //         nxt = 0;
        //     }

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

    assert(accumulate(all(flipped),0ll) == 0);

    pending.pb({0,0});

    if(last_type == 0){
        sx[-last_guy] = pending.front().ff;
    }
    else if(last_type == 1){
        sy[-last_guy] = pending.front().ff;
    }
    else{
        b[last_guy] = pending.front().ff;
    }

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

    sx.erase(sx.begin());
    sy.erase(sy.begin());
    assert(switch_ptr <= 2*n);
    answer(b,sx,sy);

    // rep1(i,siz/2-1){
    //     sx[i] = -(i*2);
    //     sy[i] = -(i*2+1);
    // }

    // rep1(iter,siz){
    //     ll ptr = 1;
    //     while(ptr < siz/2){
    //         flipped[ptr] ^= 1;
    //         if(flipped[ptr]){
    //             ptr = ptr*2;
    //         }
    //         else{
    //             ptr = ptr*2+1;
    //         }
    //     }

    //     ll nxt = 0;

    //     if(iter < n){
    //         nxt = 1;
    //     }
    //     else if(iter < siz){
    //         nxt = -1;
    //     }
    //     else{
    //         nxt = 0;
    //     }

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

    // sx.erase(sx.begin());
    // sy.erase(sy.begin());

    // answer(b,sx,sy);

    // vector<int> cnt(m+1);
    // rep(i,n) cnt[a[i]]++;
    // rep(i,m+1){
    //     if(cnt[i] == 1){
    //         a.pb(i);
    //     }
    // }

    // auto on = n;
    // n = sz(a);
    // b[0] = a[0];
    // vector<int> switch_id(m+1,-1); // trigger i is connected to which switch?
    // int ptr = 1;

    // rep(i,n){
    //     int x = a[i];
    //     if(switch_id[x] == -1){
    //         switch_id[x] = ptr;
    //         b[x] = -ptr;
    //         sx.pb(0);
    //         sy.pb(0);
    //         if(i+1 < on){
    //             sx[ptr] = a[i+1];
    //         }
    //         else if(i+1 < n){
    //             sx[ptr] = -switch_id[a[i+1]];
    //         }
    //         ptr++;
    //     }
    //     else{
    //         b[x] = -switch_id[x];
    //         if(i+1 < on){
    //             sy[switch_id[x]] = a[i+1];
    //         }
    //         else if(i+1 < n){
    //             sy[switch_id[x]] = -switch_id[a[i+1]];
    //         }
    //     }
    // }

    // sx.erase(sx.begin());
    // sy.erase(sy.begin());
    // debug(b);
    // debug(sx);
    // debug(sy);

    // answer(b,sx,sy);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 20 ms 6880 KB Output is correct
3 Correct 16 ms 5720 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 4188 KB Output is correct
6 Correct 25 ms 8028 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 20 ms 6880 KB Output is correct
3 Correct 16 ms 5720 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 4188 KB Output is correct
6 Correct 25 ms 8028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 37 ms 7892 KB Output is correct
9 Correct 39 ms 9300 KB Output is correct
10 Correct 57 ms 11848 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 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 20 ms 6880 KB Output is correct
3 Correct 16 ms 5720 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 4188 KB Output is correct
6 Correct 25 ms 8028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 37 ms 7892 KB Output is correct
9 Correct 39 ms 9300 KB Output is correct
10 Correct 57 ms 11848 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 80 ms 13536 KB Output is correct
15 Correct 35 ms 6348 KB Output is correct
16 Correct 55 ms 9692 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 348 KB Output is correct
20 Correct 63 ms 11972 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 53 ms 5924 KB Output is correct
3 Partially correct 95 ms 10352 KB Output is partially correct
4 Partially correct 98 ms 11144 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Output is partially correct
2 Correct 53 ms 5924 KB Output is correct
3 Partially correct 95 ms 10352 KB Output is partially correct
4 Partially correct 98 ms 11144 KB Output is partially correct
5 Partially correct 101 ms 13944 KB Output is partially correct
6 Partially correct 86 ms 14704 KB Output is partially correct
7 Partially correct 87 ms 14344 KB Output is partially correct
8 Partially correct 88 ms 14648 KB Output is partially correct
9 Partially correct 92 ms 9860 KB Output is partially correct
10 Partially correct 120 ms 14956 KB Output is partially correct
11 Partially correct 104 ms 14620 KB Output is partially correct
12 Partially correct 67 ms 9904 KB Output is partially correct
13 Partially correct 57 ms 9516 KB Output is partially correct
14 Partially correct 55 ms 9456 KB Output is partially correct
15 Partially correct 54 ms 9224 KB Output is partially correct
16 Partially correct 2 ms 600 KB Output is partially correct
17 Partially correct 49 ms 7996 KB Output is partially correct
18 Partially correct 54 ms 8040 KB Output is partially correct
19 Partially correct 54 ms 8500 KB Output is partially correct
20 Partially correct 72 ms 10900 KB Output is partially correct
21 Partially correct 88 ms 13080 KB Output is partially correct
22 Partially correct 65 ms 10424 KB Output is partially correct