Submission #585499

#	Time	Username	Problem	Language	Result	Execution time	Memory
585499		79brue	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	56 ms	9568 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace nAnna{
    int n;
    int arr[100005];
    int first0=-1, last2=-1, last1=-1;

    bool bits[200005];
    ll bitSeq[2002];

    ll DP[100][2];

    ll calc(vector<bool> v){
        assert(v.size() == 63);
        ll val = 0;
        for(int i=0; i<63; i++){
            if(v[i] == 1) val += DP[63-i][0];
        }
        return val;
    }

    void Anna(int N, vector<char> _s){
        n = N;
        for(int i=0; i<n; i++) arr[i] = _s[i] - 'X';

        for(int i=0; i<n; i++) if(arr[i] == 0){
            first0 = i;
            break;
        }
        if(first0 == -1 || first0 >= n-2) return;

        DP[0][0] = 1;
        for(int i=1; i<=63; i++){
            DP[i][1] = DP[i-1][0];
            DP[i][0] = DP[i-1][0] + DP[i-1][1];
        }

        bool firstBit = (arr[first0+1] == 2);
        bits[first0] = 1;
        for(int i=first0+2; i<n; i++) if(arr[i] == 2 && arr[i+1] != 2) bits[i] = 1;

        for(int i=0; i<n; i+=63){
            bitSeq[i/63] = calc(vector<bool> (bits+i, bits+i+63));
        }
        Send(firstBit);
        for(int i=0; i<(n+62)/63; i++) for(int j=0; j<44; j++) Send((bitSeq[i] >> j) & 1);
    }
}

void Anna(int N, vector<char> S){
    return nAnna::Anna(N, S);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace nBruno{
    int n, k;
    int arr[100002];
    bool removed[100002];
    vector<int> stk;

    int last1;
    ll decode[100002];
    bool bits[100002];

    void remove(int x){
        #ifdef TEST
        printf("Remove %d\n", x);
        #endif // TEST
        Remove(x);
        removed[x] = 1;
    }

    ll DP[102][2];

    void Bruno(int _n, int _l, vector<int> _vec){
        n = _n, k = _l;
        if(!k){
            for(int i=0; i<n; i++) Remove(i);
            return;
        }
        for(int i=0; i<k; i++) arr[i] = _vec[i];

        DP[0][0] = 1;
        for(int i=1; i<=63; i++){
            DP[i][1] = DP[i-1][0];
            DP[i][0] = DP[i-1][0] + DP[i-1][1];
        }

//        assert(k == 69873);
        bool firstBit = _vec[0];

        for(int i=1, p=0; i<k; i+=44, p+=63){
            for(int j=0; j<44; j++) if(_vec[i+j]) decode[i] += (1LL<<j);
            int prv = 0;
            for(int j=0; j<63; j++){
                if(prv == 1){
                    prv = 0;
                    continue;
                }
                if(decode[i] >= DP[63-j][0]){
                    decode[i] -= DP[63-j][0];
                    prv = bits[p+j] = 1;
                }
            }
        }
        if(firstBit){
            for(int i=0; i<n; i++){
                if(bits[i]){
                    bits[i+1] = 1;
                    break;
                }
            }
        }

        int firstZero = -1;
        for(int i=0; i<n; i++){
            if(bits[i]){
                firstZero = i;
                break;
            }
        }
        for(int i=0; i<firstZero; i++) Remove(i);

        bits[n-1] = 1;
        for(int i=firstZero+1; i<n; i++){
            int j = i;
            while(!bits[j]) j++;
            for(int x=j-1; x>=i; x--) remove(x);
            remove(j);
            i=j;
        }
        remove(firstZero);
    }
}

void Bruno(int N, int L, vector<int> A){
    nBruno::Bruno(N, L, A);
}

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