Submission #547903

#	Time	Username	Problem	Language	Result	Execution time	Memory
547903		tht2005	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	60 ms	6648 KiB

Anna

#include "Anna.h"
#include <vector>

void Anna(int N, std::vector<char> S) {
    for(int i = 0; i < N; ++i) {
        if(S[i] == 'X') {
            Send(0);
            Send(0);
        }
        else if(S[i] == 'Y') {
            Send(0);
            Send(1);
        }
        else {
            Send(1);
            Send(0);
        }
    }
}

Bruno

#include "Bruno.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

bool ckmax(int& a, int b) {
    return (a < b) ? (a = b), 1 : 0;
}

void Bruno(int N, int L, std::vector<int> A) {
    assert(L == 2 * N);
    std::vector<char> S;
    for(int i = 0; i < L; i += 2) {
        if(A[i] == 0) {
            if(A[i + 1] == 0)
                S.push_back('X');
            else
                S.push_back('Y');
        }
        else {
            S.push_back('Z');
        }
    }
    assert((int)S.size() == N);
    std::vector<int> f(1 << N, -1), trc(1 << N);
    std::vector<bool> ok(N);
    char tmp;
    f.back() = 0;
    for(int t = 1 << N; t--; ) {
        if(f[t] == -1) continue;
        for(int i = N; i--; )
            ok[i] = (t >> i & 1) && (S[i] == 'Y');
        tmp = 0;
        for(int i = 0; i < N; ++i) {
            if(t >> i & 1) {
                if(ok[i] && tmp != 'X') {
                    ok[i] = 0;
                }
                tmp = S[i];
            }
        }
        tmp = 0;
        for(int i = N; i--; ) {
            if(t >> i & 1) {
                if(ok[i] && tmp != 'Z') {
                    ok[i] = 0;
                }
                tmp = S[i];
            }
        }
        for(int i = N; i--; ) {
            if(t >> i & 1) {
                int nt = t ^ (1 << i);
                if(ckmax(f[nt], f[t] + ok[i])) {
                    trc[nt] = i;
                }
            }
        }
    }
    int t = 0;
    std::vector<int> res;
    for(int i = N; i--; ) {
        int j = trc[t];
        res.push_back(j);
        assert((t >> j & 1) == 0);
        t |= 1 << j;
    }
    for(int i = N; i--; )
        Remove(res[i]);
}

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