Submission #708709

#	Time	Username	Problem	Language	Result	Execution time	Memory
708709		hngwlog	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	149 ms	4256 KiB

Anna

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

void Anna(int n, vector<char> s) {

    for (int i = 0; i < n; i++) {
        if (s[i] == 'X') Send(0), Send(0);
        else if (s[i] == 'Y') Send(0), Send(1);
        else Send(1), Send(0);
    }
}

Bruno

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

void Bruno(int n, int l, vector<int> a) {

    vector<int> f(1 << n), tr(1 << n);
    string s = "";
    for (int i = 0; i < l; i += 2) {
        if (a[i] == 0 && a[i + 1] == 0) s += 'X';
        else if (a[i] == 0 && a[i + 1]) s += 'Y';
        else s += 'Z';
    }
    for (int mask = 0; mask < (1 << n); mask++) f[mask] = - n - 5;
    f[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int mask_ = ((1 << n) - 1) ^ mask; mask_ > 0; mask_ ^= mask_ & - mask_) {
            int i = __builtin_ctz(mask_);
            int add = 0;
            if (s[i] == 'Y') {
                int minn = n, maxx = - 1;
                for (int j = 0; j < n; j++) {
                    if ((mask >> j) & 1 || j == i) continue;
                    if (j < i) maxx = max(maxx, j);
                    else minn = min(minn, j);
                }
                if (minn != n && maxx != - 1 && s[minn] == 'Z' && s[maxx] == 'X') add = 1;
            }
            if (f[mask | (1 << i)] < f[mask] + add) {
                f[mask | (1 << i)] = f[mask] + add;
                tr[mask | (1 << i)] = mask;
            }
        }
    }
    vector<int> ans;
    int x = (1 << n) - 1;
    while (x) {
        ans.push_back(__builtin_ctz(tr[x] ^ x));
        x = tr[x];
    }
    reverse(ans.begin(), ans.end());
    for (auto e: ans) Remove(e);
}

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