Submission #1169394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169394		nhphuc	Ancient Machine (JOI21_ancient_machine)	C++20	5 / 100	38 ms	6336 KiB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;

long long f[80][2];

void init (){
    f[1][0] = f[1][1] = f[2][1] = 1; f[2][0] = 2;
    for (int i = 3; i <= 79; ++i){
        f[i][0] = f[i - 1][0] + f[i - 1][1];
        f[i][1] = f[i - 1][0];
    }
    return;
}

long long find_lex (string &s, int l, int r){
    long long k = 0;
    for (int i = l; i <= r; ++i){
        if (s[i] == '1'){
            k += f[(r - i + 1)][0];
        }
    }
    return k;
}

void Anna (int n, vector<char> a){
    init();
    string s;
    bool stx = false;
    for (int i = 0; i <= n - 1; ++i){
        if (a[i] == 'X'){
            if (stx == false){
                s += "10";
                stx = true;
            } else {
                s += '0';
            }
        } else {
            if (a[i] == 'Z' && stx){
                if (s.back() == '1'){
                    s.back() = '0';
                }
                s += '1';
            } else {
                s += '0';
            }
        }
    }
    while (s.size() % 74 != 0){
        s += '0';
    }
    for (int i = 0; i < s.size(); i += 74){
        long long lex = find_lex(s, i, i + 73);
        for (int j = 0; j <= 52; ++j){
            if (lex & (1ll << j)){
                Send(1);
            } else {
                Send(0);
            }
        }
    }
}

Bruno

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

using namespace std;

long long f[80][2];

void init (){
    f[1][0] = f[1][1] = f[2][1] = 1; f[2][0] = 2;
    for (int i = 3; i <= 79; ++i){
        f[i][0] = f[i - 1][0] + f[i - 1][1];
        f[i][1] = f[i - 1][0];
    }
    return;
}

string decode_lex (long long k){
    if (f[1][0] == 0){
        init();
    }
    string ans;
    for (int i = 74; i >= 1; --i){
        if (k >= f[i][0]){
            ans += '1';
            k -= f[i][0];
        } else {
            ans += '0';
        }
    }
    return ans;
}

void Bruno (int n, int l, vector<int> a){
    init();
    string s;
    for (int i = 0; i <= l; i += 52){
        long long k = 0;
        for (int j = i; j <= i + 51; ++j){
            if (a[j]){
                k += (1ll << (j - i));
            }
        }
        s += decode_lex(k);
    }
    vector<int> pos;
    for (int i = 0; i <= n; ++i){
        if (s[i] == '1'){
            pos.push_back(i);
        }
    }
    if (pos.size() <= 1){
        for (int i = 0; i <= n - 1; ++i){
            Remove(i);
        }
        return;
    }
    for (int i = 0; i < pos[0]; ++i){
        Remove(i);
    }
    for (int i = pos.back(); i <= n - 1; ++i){
        Remove(i);
    }
    for (int i = 1; i < pos.size(); ++i){
        --pos[i];
        for (int j = pos[i] - 1; j > pos[i - 1]; --j){
            Remove(j);
        }
        Remove(pos[i]);
    }
    Remove(pos[0]);
    return;
}

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