Submission #1072778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072778		GusterGoose27	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	68 ms	9468 KiB

Anna

#include "Anna.h"

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

#define sz(s) (int(s.size()))

void Anna(int n, vector<char> S) {
    vector<int> conv;
    int p = 1;
    for (int i = 0; i < n && S[i] != 'X'; i++) S[i] = 'Y';
    int r = n-1;
    for (; r >= 0 && S[r] != 'Z'; r--) S[r] = 'Y';
    if (r < 2) return;
    for (char c: S) {
        int v = c-'X';
        if ((v&1)==(p&1)) conv.push_back(1);
        else {
            conv.push_back(v);
            p = v;
        }
    }
    bool real = S[r-1] == 'Y';
    conv.resize(r);
    conv.push_back(1);
    for (int i = 0; i < sz(conv); i++) {
        if (conv[i] == 1) Send(0);
        else {
            Send(1);
            Send(conv[i] == 2);
            i++;
        }
    }
    Send(real);
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int(s.size()))

void Bruno(int n, int l, vector<int> A) {
    if (sz(A) == 0) {
        for (int i = 0; i < n; i++) Remove(i);
        return;
    }
    vector<int> tp;
    set<int> xz, y;
    for (int i = 0; i < l-1; i++) {
        if (A[i] == 0) tp.push_back(1);
        else {
            i++;
            tp.push_back(2*A[i]);
            tp.push_back(1);
        }
    }
    int r = sz(tp)-1;
    tp[r] = 2;
    while (sz(tp) < n) tp.push_back(1);
    for (int i = 0; i < n; i++) {
        if (tp[i]&1) y.insert(i);
        else xz.insert(i);
    }
    auto del = [&](int v) {
        if (tp[v]&1) {
            if (y.find(v) == y.end()) return;
            y.erase(v);
        }
        else {
            if (xz.find(v) == xz.end()) return;
            xz.erase(v);
        }
        Remove(v);
    };
    if (!A[l-1]) {
        auto x = xz.find(r);
        int v = *(--x);
        for (; v < r; v++) del(v);
    }
    if (sz(xz) > 1) {
        int lim = *(xz.begin());
        for (int s = *(xz.begin()); s != *(xz.rbegin()); ) {
            int nxt = *(xz.upper_bound(s));
            if (nxt == r) break;
            if (tp[nxt] == 0) {
                s = nxt;
                lim = nxt;
                continue;
            }
            for (int i = lim+1; i <= nxt; i++) del(i);
            lim = nxt;
        }
        int s = *(xz.rbegin());
        lim = s;
        while (sz(xz) > 1) {
            int p = *(--xz.find(s));
            for (int i = p+1; i < lim; i++) del(i);
            del(p);
            lim = p;
        }
    }
    for (int i = 0; i < n; i++) del(i);
}

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