oj.uz

Submission #708709

# Submission time Handle Problem Language Result Execution time Memory
708709 2023-03-12T08:16:00 Z hngwlog Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 149 ms 4256 KB 
#include <bits/stdc++.h>
#include "Anna.h"
using namespace std;

void Anna(int n, 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 <bits/stdc++.h>
#include "Bruno.h"
using namespace std;

void Bruno(int n, int l, vector<int> a) {

    vector<int> f(1 << n), tr(1 << n);
    string s = "";
    for (int i = 0; i < l; i += 2) {
        if (a[i] == 0 && a[i + 1] == 0) s += 'X';
        else if (a[i] == 0 && a[i + 1]) s += 'Y';
        else s += 'Z';
    }
    for (int mask = 0; mask < (1 << n); mask++) f[mask] = - n - 5;
    f[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int mask_ = ((1 << n) - 1) ^ mask; mask_ > 0; mask_ ^= mask_ & - mask_) {
            int i = __builtin_ctz(mask_);
            int add = 0;
            if (s[i] == 'Y') {
                int minn = n, maxx = - 1;
                for (int j = 0; j < n; j++) {
                    if ((mask >> j) & 1 || j == i) continue;
                    if (j < i) maxx = max(maxx, j);
                    else minn = min(minn, j);
                }
                if (minn != n && maxx != - 1 && s[minn] == 'Z' && s[maxx] == 'X') add = 1;
            }
            if (f[mask | (1 << i)] < f[mask] + add) {
                f[mask | (1 << i)] = f[mask] + add;
                tr[mask | (1 << i)] = mask;
            }
        }
    }
    vector<int> ans;
    int x = (1 << n) - 1;
    while (x) {
        ans.push_back(__builtin_ctz(tr[x] ^ x));
        x = tr[x];
    }
    reverse(ans.begin(), ans.end());
    for (auto e: ans) Remove(e);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2596 KB Output is correct
2 Correct 53 ms 2556 KB Output is correct
3 Correct 64 ms 2564 KB Output is correct
4 Correct 31 ms 2556 KB Output is correct
5 Correct 60 ms 2564 KB Output is correct
6 Correct 36 ms 2564 KB Output is correct
7 Correct 0 ms 508 KB Output is correct
8 Correct 0 ms 516 KB Output is correct
9 Correct 7 ms 2564 KB Output is correct
10 Correct 149 ms 2564 KB Output is correct
11 Correct 8 ms 2556 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 4256 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -