Submission #1153702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153702		aycnl	Ancient Machine (JOI21_ancient_machine)	C++20	5 / 100	28 ms	3516 KiB

Anna

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

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(998244353)
#define maxN 305

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

void Anna(int N, std::vector<char> S) {
    for (char c : S) {
        if (c == 'X') Send(0), Send(0);
        if (c == 'Y') Send(0), Send(1);
        if (c == 'Z') Send(1), Send(0);
    }
}

Bruno

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

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(998244353)
#define maxN 305

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

int n;
vi a;
int f[bit(18) + 1];

int dp(int mask) {
    if (mask == bit(n) - 1) return 0;
    if (f[mask] != -1) return f[mask];

    int res = 0;
    fto(i, 0, n-1) if (!(mask&bit(i))) {
        if (a[i] != 1) res = max(res, dp(mask|bit(i)));
        else {
            int okl = 0, okr = 0;
            fdto(j, i-1, 0) if (!(mask&bit(j))) {
                if (a[j] == 0) okl = 1;
                break;
            }
            fto(j, i+1, n-1) if (!(mask&bit(j))) {
                if (a[j] == 2) okr = 1;
                break;
            }
            res = max(res, dp(mask|bit(i)) + (okl&&okr));
        }
    }
    return f[mask] = res;
}

void Bruno(int N, int L, std::vector<int> A) {
    n = N;
    fto(i, 0, N-1) {
        if (A[i*2] == 0 && A[i*2+1] == 0) a.pb(0);
        if (A[i*2] == 0 && A[i*2+1] == 1) a.pb(1);
        if (A[i*2] == 1 && A[i*2+1] == 0) a.pb(2);
    }
    memset(f, -1, sizeof f);
    dp(0);

    int mask = 0;
    while (1) {
        if (mask == bit(n) - 1) break;
        fto(i, 0, n-1) if (!(mask&bit(i))) {
            if (a[i] != 1) {
                if (dp(mask) == dp(mask|bit(i))) {
                    Remove(i);
                    mask |= bit(i);
                    break;
                }
            } else {
                int okl = 0, okr = 0;
                fdto(j, i-1, 0) if (!(mask&bit(j))) {
                    if (a[j] == 0) okl = 1;
                    break;
                }
                fto(j, i+1, n-1) if (!(mask&bit(j))) {
                    if (a[j] == 2) okr = 1;
                    break;
                }
                if (dp(mask) == dp(mask|bit(i)) + (okl && okr)) {
                    Remove(i);
                    mask |= bit(i);
                    break;
                }
            }
        }
    }
}

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