Submission #1073670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073670		GusterGoose27	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	63 ms	9784 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 (int i = r-1; i > 0 && S[i] != 'Y'; i--) S[i] = 'X';
    for (char c: S) {
        int v = c-'X';
        if ((v&1)==(p&1)) conv.push_back(1);
        else {
            conv.push_back(v);
            p = v;
        }
    }
    conv.resize(r);
    conv.push_back(1);
    vector<int> gold_code; // 0 -> XY, 1 -> ZY, 2 -> YXY
    for (int i = 0; i < sz(conv);) {
        if (conv[i] != 1) {
            assert(i < sz(conv)-1);
            assert(conv[i+1] == 1);
            gold_code.push_back(conv[i]/2);
            i += 2;
        }
        else {
            if (i == sz(conv)-1) break;
            if (conv[i+1] == 1) {
                conv[i] = 2;
                gold_code.push_back(1);
                i += 2;
            }
            else if (conv[i+1] == 2) {
                swap(conv[i], conv[i+1]);
                gold_code.push_back(1);
                i += 2;
            }
            else {
                assert(i < sz(conv)-2);
                assert(conv[i+2] == 1);
                gold_code.push_back(2);
                i += 3;
            }
        }
    }
    bool ex = (conv.end()[-2] == 1);
    if (ex) conv.pop_back();
    for (int i = 0; i < sz(conv); i++) {
        if (conv[i] == 1) Send(0);
        else {
            Send(1);
            Send(conv[i] == 2);
            i++;
        }
    }
    Send(ex);
}

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 + A[l-1];
    if (A[l-1]) tp.push_back(2);
    else 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 (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