oj.uz

Submission #710422

# Submission time Handle Problem Language Result Execution time Memory
710422 2023-03-15T08:32:17 Z tanprodium Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 84 ms 7048 KB 
#include "Anna.h"
#include<bits/stdc++.h>

using namespace std;

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

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);
    }
}

/*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;
}*/

#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;

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

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);
}

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

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2568 KB Output is correct
2 Correct 84 ms 2572 KB Output is correct
3 Correct 77 ms 2556 KB Output is correct
4 Correct 78 ms 2564 KB Output is correct
5 Correct 75 ms 2556 KB Output is correct
6 Correct 73 ms 2568 KB Output is correct
7 Correct 0 ms 516 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 66 ms 2568 KB Output is correct
10 Correct 67 ms 2556 KB Output is correct
11 Correct 66 ms 2556 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 7048 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -