Submission #710524

#	Time	Username	Problem	Language	Result	Execution time	Memory
710524		tanprodium	Ancient Machine (JOI21_ancient_machine)	C++17	69 / 100	61 ms	8320 KiB

Anna

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

using namespace std;

const int LOG = 17;

int cnt = 0;

/*void Send(int a) {
    ++cnt;
    cout << a << ' ';
}*/

void tobit(int x) {
    for (int i = 0; i < LOG; i++) {
        int bit = (x >> i & 1);

        Send(bit);
    }
}

void Anna(int N, vector<char> S) {
    string s = "";

    for (int i = 0; i < N; i++) s += S[i];

    int sz = N;

    int u = -1, v = -1;

    for (int i = 0; i < N; i++)
    if (s[i] == 'X') {
        u = i;
        break;
    }

    for (int i = sz - 1; i >= 0; i--)
    if (s[i] == 'Z') {
        v = i;
        break;
    }

    if (u == -1 || v == -1 || (u > v)) {
        tobit((1 << LOG) - 1);
        return;
    }

    tobit(u);
    tobit(v);

    for (int i = u; i <= v; i++) {
        if (s[i] == 'Z') Send(1);
        else Send(0);
    }
}

/*void solve() {
    int n;
    string s;
    vector<char> vs;
    cin >> n >> s;

    for (int i = 0; i < n; i++)
        vs.push_back(s[i]);

    Anna(n, vs);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}*/

Bruno

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

using namespace std;

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

const int oo = 1e9;
const int LOG = 17;

/*void Remove(int d) {
    cout << d << ' ';
}*/

// sub1

/*void Bruno(int N, int L, vector<int> A) {
    string s = "";

    for (int i = 0; i < L; i += 2) {
        if (A[i] == 0) {
            if (A[i + 1] == 0)
                s += 'X';
            else s += 'Y';
        } else s += 'Z';
    }

    int sz = N;
    int all = (1 << sz);
    vector<int> dp(all + 5, -oo), rem(all + 5, 0);
    dp[0] = 0;

    for (int mask = 0; mask < all; mask++) {
        vector<int> pos;

        for (int i = 0; i < sz; i++)
            if (!(mask >> i & 1))
                pos.push_back(i);

        int spos = (int)pos.size();

        for (int i = 0; i < spos; i++) {
            bool good = false;
            int cur = pos[i];

            if (i > 0 && i < spos - 1) {
                int pre = pos[i - 1];
                int suf = pos[i + 1];

                if (s[pre] == 'X' && s[cur] == 'Y' && s[suf] == 'Z')
                    good = true;
            }

            int nmask = mask | (1 << cur);

            if (maximize(dp[nmask], dp[mask] + good))
                rem[nmask] = cur;
        }
    }

    vector<int> ans;

    int mask = all - 1;
    while (mask) {
        int bit = rem[mask];
        ans.push_back(bit);
        mask ^= (1 << bit);
    }

    reverse(ans.begin(), ans.end());

    for (int x : ans) Remove(x);
}*/

// sub2

void Remseg(int l, int r) {
    if (l > r) return;
    for (int i = l; i <= r; i++) Remove(i);
}

void Bruno(int N, int L, vector<int> A) {
    bool ok = false;

    for (int i = 0; i < LOG; i++)
    if (A[i] == 0) {
        ok = true;
        break;
    }

    int sz = N;

    if (!ok) {
        Remseg(0, sz - 1);
        return;
    }

    int u = 0, v = 0;

    for (int i = 0; i < LOG; i++) {
        u += A[i] * (1 << i);
    }

    for (int i = LOG; i < 2 * LOG; i++) {
        v += A[i] * (1 << (i - LOG));
    }

    Remseg(0, u - 1);
    Remseg(v + 1, sz - 1);

    stack<int> inSta;

    for (int i = 2 * LOG; i < L; i++) {
        int cur = u + i - 2 * LOG;

        if (A[i] == 1) {
            while ((inSta.size() > 1)) {
                int pos = inSta.top();
                inSta.pop();

                Remove(pos);
            }

            Remove(cur);
        } else inSta.push(cur);
    }

    Remove(u);
}

/*void solve() {
    int n;
    int l;
    vector<int> a;

    cin >> n >> l;

    for (int i = 1; i <= l; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    Bruno(n, l, a);
}

int main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);
    solve();
    return 0;
}*/

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