Submission #475436

#	Time	Username	Problem	Language	Result	Execution time	Memory
475436		balbit	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	79 ms	9088 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif






namespace {

const int maxn = 1e5+5;
const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


}

//#ifdef BALBIT
//void Send(int x) {
//    bug("Sent: ", x);
//}
//#endif // BALBIT

ull fib[100];


void Anna(int n, std::vector<char> S) {

    vector<int> ret(n);
    bool zed = 0;
    int wherezed = n;
    for (int i = n-1; i>=0; --i) {
        if (S[i] == 'Z' && !zed) {
            zed = 1;
            wherezed = i;
        }
        else if (S[i] == 'X' && zed && (i==0 || S[i-1] != 'X')) {
            ret[i] = 1;
        }
    }

    // Send wherezed
    REP(i, 17) {
        Send((wherezed>>i)&1);
    }

    fib[0] = 1; fib[1] = 1;

    for (int i = 2; i<=63; ++i) {
        fib[i] = fib[i-1] + fib[i-2];
//        bug(i, ULLONG_MAX,fib[i]);
    }
    bug(__lg(fib[63]));

//    bug(__lg(fib[64]));



    for (int i = 0; i<n; i+=63) {

        ll tmp = 0;
        REP(j,63) {
            if ((i+j) < n && ret[i+j]) tmp += fib[j+1];
        }
        REP(j, 44) {
            Send((tmp >> j) & 1);
        }
    }

}



//int main(){
//    Anna(6, {'Z','X','Y','X','Z','Z'});
//}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")

using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif



namespace {

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;

const int maxn = 2e5+5;

int far[maxn];
ll fib[100];

}  // namespace



void Bruno(int n, int L, std::vector<int> A) {

//    if (*max_element(ALL(A)) == 0) {
//    }

    int zpos = 0;
    REP(i,17){
        zpos += A[i] << i ;
    }

    fib[0] = fib[1] = 1;
    for (int i = 2; i<=63; ++i) fib[i] = fib[i-1] + fib[i-2];
    if (zpos == n) {
        REP(i,n) {
            Remove(i);
        }
        return;
    }
    bug(zpos);
    vector<int> rest;
    for (int i = 17; i<SZ(A); ++i) {
        rest.pb(A[i]);
    }

    for (int i = 0; i<SZ(rest); i+=44) {
        ll tt = 0;
        REP(j,44) {
            if ((i+j<SZ(rest)) && rest[i+j]) tt += 1ll<<j;
        }
        bug(i,tt);
        for (int j = 63; j>=1; --j) {
            if (tt >= fib[j]) {
                tt -= fib[j];
                if (i != 0)
                bug(i,j);
                far[(i/44)*63+j-1] = 1;
            }

        }

    }


    vector<int> Yay;
    int tit = 0;
    while (SZ(Yay) < n) {
        if (far[tit]) {
            Yay.pb(1);
        }
        else Yay.pb(0);
        bug(tit, Yay.back());
        ++tit;
    }

    Yay[zpos] = 1;
    bug(zpos);


    for (int i = n-1; i>=0; --i) {
        if (Yay[i] == 1) {
            zpos = i;
            break;
        }else{
            Remove(i);
        }
    }



    int prv = zpos;
    for (int i = zpos-1; i>=0; --i) {
        if (Yay[i] == 1 || i == 0) {
            // met an x
            for (int j = i+1; j<prv; ++j) {
                Remove(j);
            }
            Remove(i);
            prv = i;
        }
    }
    Remove(zpos);



}

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