Submission #926793

# Submission time Handle Problem Language Result Execution time Memory
926793 2024-02-13T18:03:14 Z GrindMachine Mechanical Doll (IOI18_doll) C++17
2 / 100
53 ms 11332 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{
                b[x] = 0;
                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());
    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);
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 19 ms 5468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 4188 KB Output is correct
6 Correct 27 ms 8028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 19 ms 5468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 4188 KB Output is correct
6 Correct 27 ms 8028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 53 ms 11332 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 19 ms 5468 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 4188 KB Output is correct
6 Correct 27 ms 8028 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Incorrect 53 ms 11332 KB Output isn't correct
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -