Submission #1159446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159446		SmuggingSpun	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	42 ms	6316 KiB

Anna

#include<bits/stdc++.h>
#include "Anna.h"
using namespace std;
typedef long long ll;
void Anna(int n, vector<char>s) {
    const int MAX_BIT = 62;
    vector<ll>fib = {1, 2};
    while(true){
        ll x = fib.back() + fib[int(fib.size()) - 2];
        if(x >= (1LL << MAX_BIT)){
            break;
        }
        fib.emplace_back(x);
    }
    fib.pop_back();
    const int LIM = fib.size();
    vector<bool>a(n + 1, false);
    for(int i = 0; i < n; i++){
        if(s[i] == 'X'){
            a[i] = true;
            for(int j = i + 1; j < n; j++){
                if(s[j] == 'Z'){
                    while(j < n && s[j] == 'Z'){
                        j++;
                    }
                    a[j] = true;
                    while(j < n && s[j] != 'Z'){
                        j++;
                    }
                    j--;
                }
            }
            break;
        }
    }
    while(a.size() % LIM != 0){
        a.emplace_back(false);
    }
    for(int i = 0; i < a.size(); i += LIM){
        ll dict = 0;
        for(int j = 0; j < LIM; j++){
            if(a[i + j]){
                dict += fib[j];
            }
        }
        for(int i = 0; i < MAX_BIT; i++){
            Send((1 << i & dict) ? 1 : 0);
        }
    }
}

Bruno

#include<bits/stdc++.h>
#include "Bruno.h"
using namespace std;
typedef long long ll;
void Bruno(int n, int L, vector<int>A){
    const int MAX_BIT = 62;
    vector<ll>fib = {1, 2};
    while(true){
        ll x = fib.back() + fib[int(fib.size()) - 2];
        if(x >= (1LL << MAX_BIT)){
            break;
        }
        fib.emplace_back(x);
    }
    fib.pop_back();
    const int LIM = fib.size();
    vector<bool>a;
    for(int i = 0; i < L; i += MAX_BIT){
        ll dict = 0;
        for(int j = 0; j < MAX_BIT; j++){
            if(A[i + j] == 1){
                dict |= 1 << j;
            }
        }
        vector<bool>app;
        for(int j = LIM - 1; j > -1; j--){
            if(fib[j] <= dict){
                dict -= fib[j--];
                app.emplace_back(true);
            }
            app.emplace_back(false);
        }
        for(int j = LIM - 1; j > -1; j--){
            a.emplace_back(app[j]);
        }
    }
    for(int i = 0; i < n; i++){
        if(a[i]){
            int I = i;
            bool need = true;
            for(int j = i + 1; j <= n; j++){
                if(a[j]){
                    need = false;
                    for(int k = j - 2; k > i; k--){
                        Remove(k);
                    }
                    Remove(j - 1);
                    int nxt_j = -1;
                    for(int t = j + 1; t <= n; t++){
                        if(a[t]){
                            nxt_j = t;
                            break;
                        }
                    }
                    if(nxt_j == -1){
                        for(int t = j; t < n; t++){
                            Remove(t);
                        }
                        break;
                    }
                    i = j - 1;
                    j = nxt_j - 1;
                }
            }
            if(need){
                for(int j = i + 1; j < n; j++){
                    Remove(j);
                }
            }
            Remove(I);
            break;
        }
        else{
            Remove(i);
        }
    }
}

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