Submission #996680

#	Time	Username	Problem	Language	Result	Execution time	Memory
996680		hotboy2703	Ancient Machine (JOI21_ancient_machine)	C++17	97 / 100	44 ms	10652 KiB

Anna

#include "Anna.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

namespace A{
    const ll BIG = 14;
    const ll SMALL = 10;
    struct pt{
        ll type,l,r;
    };
    vector <ll> all;
    void init(){
        for (ll i = 0;i < MASK(BIG);i ++){
            bool ok = 1;
            for (ll j = 1;j < BIG;j ++){
                if (BIT(i,j)&&BIT(i,j-1))ok = 0;
            }
            if (ok)all.push_back(i);
        }
    }
}

void Anna(int N, std::vector<char> S) {
    using namespace A;
    vector <ll> a;
    for (ll i = 0;i < N;i ++){
        a.push_back(S[i]-'X');
    }
//    for (auto x:a)cout<<x<<' ';
//    cout<<'\n';
    vector <ll> res(N+BIG);
    vector <pt> nw;
    for (ll i = 0;i < N;i ++){
        ll j = i;
        while (j + 1 < N && a[j+1] == a[i])j++;
        nw.push_back({a[i],i,j});
        i = j;
    }
    while (!nw.empty() && nw.back().type != 2){
        nw.pop_back();
    }
    ll last0 = -1;
    for (ll i = 0;i < sz(nw);i ++){
        if (last0 == -1){
            if (nw[i].type == 0){res[nw[i].r] = 1;last0 = nw[i].r;}
        }
        else{
            ll j = i;
            while (nw[j].type != 2)j++;
            bool ok = 0;
            for (ll k = j-1;k >= i;k --){
                if (nw[k].type==1)ok = 1;
            }
            res[nw[j].r] = 1;
            i = j;
        }
    }
//    for (auto x:res)cout<<x<<' ';
//    cout<<'\n';
//for (ll i = 0;i < N;i ++)cout<<res[i]<<' ';
//    cout<<'\n';
    init();
    vector <ll> res2;
    if (last0 != -1){
        for (ll j = 0;j < 20;j ++)res2.push_back(BIT(last0,j));
        for (ll j = last0 + 1;j < N;j += BIG){
            ll mask = 0;
            for (ll k = 0;k < BIG;k ++){
                mask += MASK(k) * res[j+k];
            }
            mask = lower_bound(all.begin(),all.end(),mask) - all.begin();
            for (ll k = 0;k < SMALL;k ++){
                res2.push_back(BIT(mask,k));
            }
        }
    }
    else{
    }
    for (auto x:res2)Send(x);
}

Bruno

#include "Bruno.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

namespace B{
    const ll BIG = 14;
    const ll SMALL = 10;
    vector <ll> all;
    void init(){
        for (ll i = 0;i < MASK(BIG);i ++){
            bool ok = 1;
            for (ll j = 1;j < BIG;j ++){
                if (BIT(i,j)&&BIT(i,j-1))ok = 0;
            }
            if (ok)all.push_back(i);
        }
    }
}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
    using namespace B;
    init();
    vector <ll> a(N+BIG);
    if (!A.empty()){
        ll last0 = 0;
        for (ll i = 0;i < 20;i ++)last0 += MASK(i) * A[i];
//        cout<<last0<<'\n';
        a[last0] = 1;
        for (ll i = 20,ptr_a = last0 + 1;i < sz(A);i += SMALL,ptr_a += BIG){
            ll mask = 0;
            for (ll j = 0;j < SMALL;j ++)mask += MASK(j) * A[i+j];
            mask = all[mask];
            for (ll j = 0;j < BIG;j ++)a[ptr_a+j] = BIT(mask,j);
        }
    }
//    for (ll i = 0;i < N;i ++)cout<<a[i]<<' ';
//    cout<<'\n';
    vector <bool> del(N);
    ll last = -1;
    ll first = -1;
    for (ll i = 0;i < N;i ++){
        if (a[i]){
            if (first==-1)first = a[i];
            else{
                for (ll j = i - 1;j > last;j --){del[j] = 1;Remove(j);}
                del[i] = 1;Remove(i);
            }
            last = i;
        }
    }
    for (ll i = 0;i < N;i ++){
        if (!del[i]){
            Remove(i);
        }
    }
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:59:18: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   59 |             bool ok = 0;
      |                  ^~

• Subtask 1: 5 / 5
• Subtask 2: 92 / 95