Submission #1168169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168169		12345678	Ancient Machine (JOI21_ancient_machine)	C++17	99 / 100	47 ms	7244 KiB

Anna

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

#define ll long long

using namespace std;

namespace anna
{
    const int nx=1e5, g=500, sz=35, base=(1<<10);

    int a[nx+5], st=-1, nxt, cnt;

    struct bignum
    {
        vector<int> v;
        bignum(int x=0)
        {
            v.resize(sz, 0);
            v[0]=x;
        }
        void add(bignum &o)
        {
            int carry=0;
            for (int i=0; i<sz; i++)
            {
                this->v[i]+=o.v[i]+carry;
                if (this->v[i]>=base) this->v[i]-=base, carry=1;
                else carry=0;
            }
        }
        void subtract(bignum &o)
        {
            int carry=0;
            for (int i=0; i<sz; i++)
            {
                this->v[i]-=o.v[i]+carry;
                if (this->v[i]<0) this->v[i]+=base, carry=1;
                else carry=0;
            }
        }
    } fib[g];
}


void Anna(int N, std::vector<char> S) {
    using namespace anna;
    while (S.size()<nx) S.push_back('X');
    S.push_back('A');
    for (int i=0; i<nx; i++)
    {
        if (S[i]=='X'&&st==-1) st=i, a[i]=1;
        if (S[i]=='Z'&&st!=-1&&(S[i+1]!='Z')) a[i]=1; 
    }
    for (int i=0; i<nx; i++)
    {
        if (a[i])
        {
            nxt=a[i+1];
            a[i+1]=0;
            break;
        }
    }
    //for (int i=0; i<N; i++) cout<<"anna "<<i<<' '<<a[i]<<'\n';
    fib[0]=bignum(1);
    fib[1]=bignum(2);
    for (int i=2; i<g; i++) fib[i]=fib[i-1], fib[i].add(fib[i-2]);
    for (int i=0; i<nx; i+=g)
    {
        //cout<<"debug "<<i<<' '<<cnt<<'\n';
        bignum tmp=bignum(0);
        for (int j=i; j<i+g; j++) if (a[j]) tmp.add(fib[j-i]); //cout<<"tmp "<<tmp.v[0]<<'\n';
        for (int j=0; j<sz; j++) for (int k=0; k<10; k++) ++cnt, Send((tmp.v[j]>>k)&1);
    }    
    Send(nxt);
}

/*
5
X Z Y Z Y
*/

Bruno

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

using namespace std;

namespace bruno
{
    const int nx=1e5, g=500, sz=35, base=(1<<10);

    int a[nx+5], st=-1, nxt, rem[nx];

    struct bignum
    {
        vector<int> v;
        bignum(int x=0)
        {
            v.resize(sz, 0);
            v[0]=x;
        }
        void add(bignum &o)
        {
            int carry=0;
            for (int i=0; i<sz; i++)
            {
                this->v[i]+=o.v[i]+carry;
                if (this->v[i]>=base) this->v[i]-=base, carry=1;
                else carry=0;
            }
        }
        void subtract(bignum &o)
        {
            int carry=0;
            for (int i=0; i<sz; i++)
            {
                this->v[i]-=o.v[i]+carry;
                if (this->v[i]<0) this->v[i]+=base, carry=1;
                else carry=0;
            }
        }
        int greater(bignum &o)
        {
            for (int i=sz-1; i>=0; i--)
            {
                if (this->v[i]>o.v[i]) return 1;
                if (this->v[i]<o.v[i]) return 0;
            }
            return 1;
        }
    } fib[g];
}

void Bruno(int N, int L, std::vector<int> A) {
    using namespace bruno;
    nxt=A.back();
    A.pop_back();
    int cur=0;
    fib[0]=bignum(1);
    fib[1]=bignum(2);
    for (int i=2; i<g; i++) fib[i]=fib[i-1], fib[i].add(fib[i-2]);
    for (int i=0; i<nx; i+=g)
    {
        bignum x=bignum(0);
        for (int j=0; j<sz; j++) for (int k=0; k<10; k++) if (A[cur++]) x.v[j]|=(1<<k); //cout<<"here "<<x.v[0]<<'\n';
        for (int j=g-1; j>=0; j--) if (x.greater(fib[j])) x.subtract(fib[j]), a[i+j]=1;
    }
    for (int i=0; i<N; i++) 
    {
        if (a[i]) 
        {
            a[i+1]=nxt;
            break;
        }
    }
    int st=-1, lst=-1;
    for (int i=0; i<N; i++)
    {
        //cout<<"bruno "<<i<<' '<<a[i]<<'\n';
        if (a[i])
        {
            if (st==-1) lst=st=i;
            else
            {
                for (int j=i-1; j>lst; j--) rem[j]=1, Remove(j);
                lst=i;
                rem[i]=1, Remove(i);
            }
        }
    }
    for (int i=0; i<N; i++) if (!rem[i]) Remove(i);
}

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