Submission #1136991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136991		adaawf	Ancient Machine (JOI21_ancient_machine)	C++20	100 / 100	50 ms	7140 KiB

Anna

#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;
string res = "";
long long int f[105];
void Anna(int n, vector<char> s) {
    vector<int> v;
    int fl = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'X' && fl == 0) {
            fl = 1;
            v.push_back(1);
            v.push_back(0);
        }
        else if (s[i] == 'Z' && fl == 1) {
            if (i + 1 < s.size() && s[i + 1] == 'Z') {
                v.push_back(0);
            }
            else v.push_back(1);
        }
        else v.push_back(0);
    }
    while (v.size() % 63 != 0) v.push_back(0);
    f[0] = 1; f[1] = 2;
    for (int i = 2; i <= 63; i++) f[i] = f[i - 1] + f[i - 2];
    for (int i = 0; i < v.size(); i += 63) {
        long long int c = 0;
        for (int j = 0; j < 63; j++) {
            if (v[i + j] == 1) {
                c += f[j];
            }
        }
        for (int i = 0; i < 44; i++) {
            if (c & (1ll << i)) {
                Send(1);
            }
            else Send(0);
        }
    }
    for (int i = 0; i <= 16; i++) {
        if (n & (1 << i)) Send(1);
        else Send(0);
    }
}

Bruno

#include <bits/stdc++.h>
#include "Bruno.h"
using namespace std;
long long int f[105], res[200005];
void Bruno(int n, int l, vector<int> v) {
    vector<int> vv;
    f[0] = 1; f[1] = 2;
    for (int i = 2; i <= 63; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    for (int i = 0; i < l - 17; i += 44) {
        long long int h = 0;
        for (int j = 0; j < 44; j++) {
            if (v[i + j] == 1) {
                h += (1ll << j);
            }
        }
        for (int j = 63; j >= 0; j--) {
            if (h >= f[j]) {
                h -= f[j];
                res[i / 44 * 63 + j] = 1;
            }
        }
    }
    int flag = 0;
    for (int i = 0; i <= (l - 17) / 44 * 63; i++) {
        if (res[i] == 1) {
            vv.push_back(i - flag);
            flag = 1;
        }
    }
    int nn = 0;
    for (int i = 0; i <= 16; i++) {
        if (v[l - 17 + i] == 1) {
            nn += (1 << i);
        }
    }
    if (vv.empty()) {
        for (int i = 0; i < nn; i++) Remove(i);
        return;
    }
    for (int i = 1; i < vv.size(); i++) {
        for (int j = vv[i] - 1; j > vv[i - 1]; j--) Remove(j);
        Remove(vv[i]);
    }
    for (int i = 0; i <= vv[0]; i++) Remove(i);
    for (int i = vv.back() + 1; i < nn; i++) Remove(i);
}

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