Submission #1056809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056809		Double_Slash	Ancient Machine (JOI21_ancient_machine)	C++17	100 / 100	35 ms	8104 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
ll dp[63] = {1, 2};
 
void precomp() { for (int i = 2; i < 63; ++i) dp[i] = dp[i - 1] + dp[i - 2]; }
 
void Anna(int N, vector<char> S) {
    precomp();
    vector<bool> bits;
    bool x = false;
    char last = 0;
    for (char c: S) {
        if (x) {
            if (c == 'Z') {
                if (last == 'Z') bits.back() = 0;
                bits.emplace_back(1);
            } else bits.emplace_back(0);
        }
        else if (c == 'X') x = true, bits.emplace_back(1), bits.emplace_back(0);
        else bits.emplace_back(0);
        last = c;
    }
    while (bits.size() % 63) bits.emplace_back(0);
    function<ll(ll, int)> encode = [&] (ll x, int i) {
        if (i < 0) return 0ll;
        if ((x >> i) & 1) return dp[i] + encode(x, i - 2);
        else return encode(x, i - 1);
    };
    for (int i = 0; i * 63 < bits.size(); ++i) {
        ll hash = 0;
        for (int j = 0; j < 63; ++j) hash |= (ll) bits[i * 63 + j] << j;
        hash = encode(hash, 62);
        for (int j = 0; j < 44; ++j) Send((hash >> j) & 1);
    }
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
ll dp[63] = {1, 2};
 
void precomp() { for (int i = 2; i < 63; ++i) dp[i] = dp[i - 1] + dp[i - 2]; }
 
void Bruno(int N, int L, vector<int> A) {
    precomp();
    vector<bool> bits;
    function<ll(ll, int)> decode = [&] (ll x, int i) {
        if (i < 0) return 0ll;
        if (x < dp[i]) return decode(x, i - 1);
        else return (1ll << i) | decode(x - dp[i], i - 2);
    };
    for (int i = 0; i * 44 < L; ++i) {
        ll hash = 0;
        for (int j = 0; j < 44; ++j) hash |= (ll) A[i * 44 + j] << j;
        hash = decode(hash, 62);
        for (int j = 0; j < 63; ++j) bits.emplace_back((hash >> j) & 1);
    }
    int x = N;
    vector<int> batch;
    for (int i = 0; i <= N; ++i) {
        if (i == N and x == N) break;
        if (x < N and bits[i]) {
            for (; batch.size() > 1 and batch.back() > x; batch.pop_back()) Remove(batch.back());
            Remove(i - 1);
            continue;
        }
        if (x < N) {
            if (i - 1 != x) batch.push_back(i - 1);
        } else {
            batch.push_back(i);
            if (bits[i]) x = i;
        }
    }
    for (int i: batch) Remove(i);
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:33:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i * 63 < bits.size(); ++i) {
      |                     ~~~~~~~^~~~~~~~~~~~~

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