Submission #1156963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156963		davele	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	41 ms	6764 KiB

Anna

#ifndef davele
#include "Anna.h"
#endif // davele

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////
const int limit = 1e5+5, compressed_len = 43, ini_len = 63;

string s;
    long long fib[1000];
    int ans[limit];

    void prep(){
        fib[0] = 1;
        fib[1] = 2;
        fib[2] = 3;
        for (int i=3; i<=91; i++) fib[i] = fib[i-1]+fib[i-2];
        //
    }

    long long trans_to_int (int l, int r){
        int len = r-l+1;
//        for (int i=0; i<=len; i++) cerr<<i<<" "<<fib[i]<<"\n";
        long long ranks = 1;
        for (int i=l; i<=r; i++){
//            cerr<<ans[i]<<" ";
            len--;
            if (ans[i]==1){
                ranks+=fib[len];
            }
        }
//        cerr<<"\n";
//        cerr<<ranks<<"\n";
        return ranks;
    }

    int curpos;

    void Anna (int n, std::vector<char> S){
        curpos = 0;
        prep();
        string s=" ";
        for (char x:S) s+=x;
        int last = n;
        for (int i=0; i<=n; i++){
            if (i!=n && s[i+1]=='X'){
                ans[curpos++] = 1;
                last = i;
                break;
            }
            ans[curpos++] = 0;
        }
        if (last!=n){
            for (int i=last+1; i<=n; i++){
                if (s[i]=='Z'){
                    if (i==n || s[i+1]!='Z') ans[curpos++] = 1;
                    else ans[curpos++] = 0;
                }
                else ans[curpos++] = 0;
            }
        }
        // for (int i=0; i<curpos; i++) cerr<<ans[i];
        // cerr<<"\n";
        for (int i=0; i<=n; i+=63){
            long long tmp = trans_to_int (i, min(n, i+63-1));
            for (int j=0; j<=43; j++) if (MASK(j)&tmp) Send(1);
            else Send(0);
        }
    }

Bruno

#ifndef davele
#include "Bruno.h"
#endif // davele


#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

//const int mod = ;
//void add (int &a, const int&b){
//    a+=b;
//    if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
//    a-=b;
//    if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
//    a*=b;
//    a%=mod;
//}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////
const int limit = 1e5+5, compressed_len = 44, ini_len = 63;

long long fib[1000];
    int b[limit];
    int N;
    int len = 0;

    void decode( long long val){
        // cerr<<val<<"\n";
        string tmp  ="";
        for (int i=63; i>=1; i--){
            if (val>fib[i-1]){
                tmp+="1";
                val-=fib[i-1];
            }
            else tmp+="0";
        }
        // cerr<<tmp<<"\n";
        if (len+62<=N){
            for (char x:tmp) b[len++] = x-'0';
        }
        else{
            int st = 63-(N-len)+1;
            for (int i=st; i<=63; i++) b[len++] = tmp[i-1]-'0';
        }
        // for (int i=0; i<len; i++) cerr<<b[i];
        // cerr<<"\n";
    }

    void prep(){
        fib[0] = 1;
        fib[1] = 2;
        fib[2] = 3;
        for (int i=3; i<=91; i++) fib[i] = fib[i-1]+fib[i-2];
        //
    }

    void Bruno (int n, int l, std::vector<int> tmp){
        N = n+1;
        len = 0;
        prep();
        //
        int numloop = l/44;
        int curbit = 0;
        //
        for (int loop = 1; loop<=numloop; loop++){
            long long encode_val  = 0;
            for (int i=0; i<=43; i++){
//                cerr<<tmp[curbit];
                encode_val += tmp[curbit]*MASK(i);
                curbit++;
            }
//            cerr<<"\n";
            decode(encode_val);
        }
//        cerr<<"ok";
        //

        bool have1 = false;
        if (b[n]==1){
          have1 = true;
        }
        for (int i = n; i>0; i--){
            if (have1) break;
            if (b[i-1]==1){
                have1 = true;
                break;
            }
            Remove(i-1);
        }
        if (!have1) return;
        for (int i=0; i<n; i++){
            if (b[i]==1){
                break;
            }
            Remove(i);
        }
        vector <int> list1;
        for (int i=0; i<=n; i++) if (b[i]==1){
          list1.pb(i-1);
          if (list1.size()==1) list1.back()++;
        }
        if (list1.size()>1 && list1.back()+1<n){
          Remove (list1.back()+1);
        }
        for (int i=1; i<list1.size(); i++){
            int st = list1[i-1]+1;
            int en = list1[i]-1;
            for (int j=en; j>=st; j--) Remove(j);
            Remove(list1[i]);
        }
        Remove(list1[0]);
    }

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