Submission #1060458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060458		GrindMachine	Broken Device (JOI17_broken_device)	C++17	100 / 100	31 ms	2880 KiB

Anna

#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) 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

/*

refs:
https://ivaniscoding.wordpress.com/2018/08/25/communication-3-broken-device/
https://oj.uz/submission/284732

*/

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

#include "Annalib.h"

static vector<int> here[15];
static vector<int> final_here[15];

static void go(int i, int take_mask){
    if(!final_here[1].empty()) return;

    if(i > 6){
        bool ok = true;

        rep(blocked,3){
            bool z = false, o = false;
            bool zz = false, zo = false;

            rep1(mask,7){
                if(mask&(1<<blocked)) conts;
                if(count(all(here[1]),mask)){
                    z = true;
                }
                if(count(all(here[2]),mask)){
                    o = true;
                }
                if(count(all(here[3]),mask)){
                    zz = true;
                }
                if(count(all(here[4]),mask)){
                    zo = true;
                }
            }

            if(zz and zo){
                z = true;
            }

            if(!z or !o){
                ok = false;
            }
        }

        if(ok){
            rep1(j,6){
                final_here[j] = here[j];
            }
        }

        return;
    }

    if(i != 2){
        rep(mask,8){
            if(take_mask&(1<<mask)) conts;
            here[i].pb(mask);
            go(i+1,take_mask|(1<<mask));
            here[i].pop_back();
        }   
    }
    else{
        rep(mask1,8){
            rep(mask2,8){
                if(take_mask&(1<<mask1)) conts;
                if(take_mask&(1<<mask2)) conts;
                here[i].pb(mask1);
                here[i].pb(mask2);
                go(i+1,take_mask|(1<<mask1)|(1<<mask2));
                here[i].pop_back();
                here[i].pop_back();
            }
        }
    }
}

const int B = 60;

void Anna( int n, long long X, int k, int a[] ){
    vector<bool> blocked(n);
    rep(i,k) blocked[a[i]] = 1;

    vector<int> send;
    rev(bit,B-1,0){
        if(X&(1ll<<bit)){
            send.pb(1);
        }
        else{
            send.pb(0);
        }
    }
    send.pb(0);

    go(1,1);
    rep1(j,6) here[j] = final_here[j];

    int ptr = 0;
    vector<int> s(n);

    auto f = [&](int i, int mask){
        int b = 0;
        rev(j,i+2,i){
            int x = 0;
            if(mask&(1<<b)) x = 1;
            s[j] = x;
            b++;
        }
    };

    for(int i = 0; i < n and ptr < B; i += 3){
        int block_cnt = 0;
        for(int j = i; j < i+3; ++j){
            block_cnt += blocked[j];
        }

        if(block_cnt >= 2) conts;

        if(block_cnt == 1){
            int x = send[ptr];
            int y = x<<1|send[ptr+1];
            y += 3;

            vector<pii> v;
            if(x == 1){
                v.pb({here[2][0],1});
                v.pb({here[2][1],1});
            }
            else{
                v.pb({here[1][0],1});
                v.pb({here[y][0],2});
            }

            for(auto [mask,add] : v){
                bool ok = true;
                int b = 0;
                rev(j,i+2,i){
                    if(mask&(1<<b)){
                        if(blocked[j]){
                            ok = false;
                        }
                    }
                    b++;
                }

                if(ok){
                    f(i,mask);
                    ptr += add;
                    break;
                }
            }
        }
        else{
            int val = send[ptr]<<1|send[ptr+1];
            ptr += 2;
            val += 3;
            f(i,here[val][0]);
        }
    }

    assert(ptr >= B);

    rep(i,n){
        Set(i,s[i]);
    }
}

Bruno

#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) 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

/*

refs:
https://ivaniscoding.wordpress.com/2018/08/25/communication-3-broken-device/
https://oj.uz/submission/284732

*/

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

#include "Brunolib.h"

static vector<int> here[15];
static vector<int> final_here[15];

static void go(int i, int take_mask){
    if(!final_here[1].empty()) return;

    if(i > 6){
        bool ok = true;

        rep(blocked,3){
            bool z = false, o = false;
            bool zz = false, zo = false;

            rep1(mask,7){
                if(mask&(1<<blocked)) conts;
                if(count(all(here[1]),mask)){
                    z = true;
                }
                if(count(all(here[2]),mask)){
                    o = true;
                }
                if(count(all(here[3]),mask)){
                    zz = true;
                }
                if(count(all(here[4]),mask)){
                    zo = true;
                }
            }

            if(zz and zo){
                z = true;
            }

            if(!z or !o){
                ok = false;
            }
        }

        if(ok){
            rep1(j,6){
                final_here[j] = here[j];
            }
        }

        return;
    }

    if(i != 2){
        rep(mask,8){
            if(take_mask&(1<<mask)) conts;
            here[i].pb(mask);
            go(i+1,take_mask|(1<<mask));
            here[i].pop_back();
        }   
    }
    else{
        rep(mask1,8){
            rep(mask2,8){
                if(take_mask&(1<<mask1)) conts;
                if(take_mask&(1<<mask2)) conts;
                here[i].pb(mask1);
                here[i].pb(mask2);
                go(i+1,take_mask|(1<<mask1)|(1<<mask2));
                here[i].pop_back();
                here[i].pop_back();
            }
        }
    }
}

const int B = 60;

long long Bruno( int n, int a[] ){
    go(1,1);
    rep1(j,6) here[j] = final_here[j];

    vector<int> bits[8];
    rep1(i,6){
        int x = 0;
        if(i <= 2){
            x = i-1;
            trav(j,here[i]){
                bits[j].pb(x);
            }
        }
        else{
            x = i-3;
            trav(j,here[i]){
                bits[j].pb((x&2)>0);
                bits[j].pb(x&1);
            }
        }
    }

    vector<int> b;

    for(int i = 0; i < n; i += 3){
        int mask = 0;
        for(int j = i; j < i+3; ++j){
            mask = mask<<1|a[j];
        }

        trav(bit,bits[mask]){
            b.pb(bit);
        }
    }

    ll ans = 0;
    rep(i,B){
        ans = ans<<1|b[i];
    }    

    return ans;
}

• Subtask 1: 100 / 100