Submission #1137650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137650		KhoaDuy	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	43 ms	6628 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
const int blsz=63,blcomsz=44,lim=17;
long long DP[blsz+1];
void setup(){
    DP[0]=1,DP[1]=2;
    for(int i=2;i<=blsz;i++){
        DP[i]=DP[i-1]+DP[i-2];
    }
}
string toBin(long long x,int limit){
    string s="";
    while(x>0){
        s+=((x&1)+'0');
        x>>=1;
    }
    while(s.length()<limit){
        s+='0';
    }
    reverse(s.begin(),s.end());
    return s;
}
long long toInt(string &s,int l,int r){
    long long x=0;
    for(int i=l;i<=r;i++){
        x<<=1;
        x+=(s[i]-'0');
    }
    return x;
}
void Anna(int n,vector<char> s){
    setup();
    int posX=-1,posY=-1,posZ=-1;
    for(int i=0;i<n;i++){
        if(s[i]=='X'){
            posX=i;
            break;
        }
    }
    for(int i=n-1;i>=0;i--){
        if(s[i]=='Z'){
            posZ=i;
            break;
        }
    }
    for(int i=posZ;i>=max(posX,0);i--){
        if(s[i]=='Y'){
            posY=i;
            break;
        }
    }
    if(posX==-1||posY==-1||posZ==-1){
        posX=0,posY=1,posZ=2;
    }
    string send="";
    send+=toBin(posX,lim);
    send+=toBin(posY,lim);
    send+=toBin(posZ,lim);
    int mark[n+1000]={0};
    for(int i=posX;i<posY;i++){
        if(s[i]=='Y'&&s[i+1]=='X'){
            mark[i]=1;
        }
    }
    for(int k=0;k<n;k+=blsz){
        long long pos=1;
        for(int i=k;i<k+blsz;i++){
            if(mark[i]==1){
                pos+=DP[k+blsz-1-i];
            }
        }
        send+=toBin(pos,blcomsz);
    }
    for(int i=0;i<send.size();i++){
        Send(send[i]-'0');
    }
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
const int blsz=63,blcomsz=44,lim=17;
long long DP[blsz+1];
void setup(){
    DP[0]=1,DP[1]=2;
    for(int i=2;i<=blsz;i++){
        DP[i]=DP[i-1]+DP[i-2];
    }
}
string toBin(long long x,int limit){
    string s="";
    while(x>0){
        s+=((x&1)+'0');
        x>>=1;
    }
    while(s.length()<limit){
        s+='0';
    }
    reverse(s.begin(),s.end());
    return s;
}
long long toInt(string &s,int l,int r){
    long long x=0;
    for(int i=l;i<=r;i++){
        x<<=1;
        x+=(s[i]-'0');
    }
    return x;
}
void Bruno(int n,int l,vector<int> a){
    setup();
    string trans="";
    for(int i=0;i<l;i++){
        trans+=(a[i]+'0');
    }
    bool spe[n]={false};
    spe[toInt(trans,0,lim-1)]=true;
    spe[toInt(trans,lim,2*lim-1)]=true;
    spe[toInt(trans,2*lim,3*lim-1)]=true;
    string state="";
    for(int k=3*lim;k<trans.length();k+=blcomsz){
        long long pos=toInt(trans,k,k+blcomsz-1);
        long long oripos=pos;
        assert(pos<=DP[blsz]);
        for(int len=blsz;len>0;len--){
            if(pos>DP[len-1]){
                pos-=DP[len-1];
                state+='1';
                len--;
                if(len>0){
                    state+='0';
                }
            }
            else{
                state+='0';
            }
        }
    }
    for(int i=0;i<state.length();i++){
        if(state[i]=='1'){
            spe[i]=true;
            spe[i+1]=true;
        }
    }
    for(int i=0;i<n;i++){
        if(!spe[i]){
            Remove(i);
        }
    }
    bool skip=false;
    for(int i=n-1;i>=0;i--){
        if(spe[i]){
            if(!skip){
                skip=true;
                continue;
            }
            Remove(i);
        }
    }
    for(int i=n-1;i>=0;i--){
        if(spe[i]){
            Remove(i);
            break;
        }
    }
}

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