Submission #1290379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290379		Zbyszek99	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	44 ms	6744 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int block_len = 112;
const int bits = 78;

namespace 
{
int arr[100200];
__int128_t fib[block_len+1];
}

void Anna(int N, vector<char> S) 
{
    while(siz(S)%block_len != 0) S.pb('Y');
    bool was = 0;
    int n = siz(S);
    rep(i,n) arr[i] = 0;
    fib[0] = 1;
    fib[1] = 2;
    rep2(i,2,block_len) fib[i] = fib[i-1]+fib[i-2];
    int fZ = -1;
    for(int i = n-1; i >= 0; i--)
    {
        if(!was)
        {
            if(S[i] == 'Z')
            {
                was = 1;
                arr[i] = 1;
                i--;
                fZ = i+1;
            }
        }
        else if(S[i] == 'X')
        {
            if(i == 0 || S[i-1] != 'X')
            {
                arr[i] = 1;
            }
        }
    }
    rep(i,n/block_len)
    {
        __int128_t cur = 0;
        rep2(j,i*block_len,(i+1)*block_len-1)
        {
            if(arr[j])
            {
                cur += fib[(i+1)*block_len-1-j];
            }
        }
        rep(bit,bits)
        {
            if(cur & ((__int128_t)(1LL) << (__int128_t)bit)) Send(1);
            else Send(0);
        }
    }
    if(fZ >= 1 && S[fZ-1] == 'X') Send(1);
    else Send(0);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int block_len = 112;
const int bits = 78;

namespace {
__int128_t fib[block_len+1];
int arr[100200];
}

void Bruno(int n, int L, vi A) 
{
    int blocks = (n+block_len-1)/block_len;
    fib[0] = 1;
    fib[1] = 2;
    rep2(i,2,block_len) fib[i] = fib[i-1]+fib[i-2];
    rep(i,blocks)
    {
        __int128_t cur = 0;
        int cnt = 0;
        rep2(j,i*bits,(i+1)*bits-1)
        {
            cnt++;
            if(A[j]) cur += ((__int128_t)(1) << (__int128_t)(j-i*bits));
        }
        rep(j,block_len)
        {
            if(cur < fib[block_len-1-j])
            {
                arr[i*block_len+j] = 0;
            }
            else 
            {
                arr[i*block_len+j] = 1;
                cur -= fib[block_len-1-j];
            }
        }
    }
    int pop = -1;
    rep(i,n) if(arr[i] == 1) pop = i;
    if(pop == -1)
    {
        rep(i,n) Remove(i);
        return;
    }
    for(int i = pop+1; i < n; i++) Remove(i);
    int beg = pop-1;
    if(A.back() == 1) 
    {
        Remove(pop-1);
        pop--;
    }
    for(int i = beg; i >= 0; i--)
    {
        if(arr[i])
        {
            rep2(j,i+1,pop-1)
            {
                Remove(j);
            }
            Remove(i);
            pop = i;
        }
    }
    rep(j,pop) Remove(j);
    Remove(beg+1);
}

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