Submission #1153731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153731		sunflower	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	27 ms	2376 KiB

Anna

#ifndef SUN
#include "Anna.h"
#endif // SUN

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

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

void Anna(int n, std::vector <char> s) {
    assert(n <= 18);

    for (char c : s) {
        if (c == 'X') {
            Send(0);
            Send(0);
        } else if (c == 'Y') {
            Send(0);
            Send(1);
        } else {
            Send(1);
            Send(0);
        }
    }
}

Bruno

#ifndef SUN
#include "Bruno.h"
#endif // SUN

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

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

const int N = MASK(18) + 10;
int dp[N + 2], trace[N + 2];

void Bruno(int n, int L, std::vector <int> A) {
    string s = "";
    for (int i = 0; i < (int) A.size(); i += 2) {
        int x = A[i], y = A[i + 1];
        if (x == 0 && y == 0) s += 'X';
        else if (x == 0 && y == 1) s += 'Y';
        else s += 'Z';
    }

    for (int mask = 0; mask < MASK(n); ++mask) dp[mask] = trace[mask] = -1;

    dp[0] = 0;
    for (int mask = 0; mask < MASK(n); ++mask) {
        for (int i = 0; i < n; ++i) {
            // BIT = 1 chua bi xoa else bi xoa;
            if (not BIT(mask, i)) {
                if (s[i] != 'Y') {
                    if (maximize(dp[mask ^ MASK(i)], dp[mask])) trace[mask ^ MASK(i)] = i;
                } else {
                    int l = -1, r = -1;
                    for (int j = i - 1; j >= 0; --j) if (not BIT(mask, j)) {l = j; break;}
                    for (int j = i + 1; j < n; ++j) if (not BIT(mask, j)) {r = j; break;}

                    if (~l && ~r && s[l] == 'X' && s[r] == 'Z') {
                        if (maximize(dp[mask ^ MASK(i)], dp[mask] + 1)) trace[mask ^ MASK(i)] = i;
                    } else {
                        if (maximize(dp[mask ^ MASK(i)], dp[mask])) trace[mask ^ MASK(i)] = i;
                    }
                }
            }
        }
    }


    vector <int> id;
    int mask = MASK(n) - 1;
    while (mask > 0) {
        id.push_back(trace[mask]);
        mask ^= MASK(trace[mask]);
    }

    reverse(id.begin(), id.end());
    for (int x : id) Remove(x);
}

#ifdef SUN
int main() {
    cout << "ok";
}
#endif // SUN

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