oj.uz

Submission #547903

# Submission time Handle Problem Language Result Execution time Memory
547903 2022-04-12T02:28:27 Z tht2005 Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 60 ms 6648 KB 
#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);
        }
    }
}

#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2568 KB Output is correct
2 Correct 53 ms 2568 KB Output is correct
3 Correct 60 ms 2672 KB Output is correct
4 Correct 60 ms 2560 KB Output is correct
5 Correct 53 ms 2640 KB Output is correct
6 Correct 50 ms 2572 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 52 ms 2568 KB Output is correct
10 Correct 56 ms 2560 KB Output is correct
11 Correct 49 ms 2568 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 6648 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -