Submission #647914

#	Time	Username	Problem	Language	Result	Execution time	Memory
647914		thorie	The Xana coup (BOI21_xanadu)	C++17	10 / 100	70 ms	1580 KiB

xanadu

#include "bits/stdc++.h"
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bool> on1(n + 1);
    vector<bool> on2(n + 1);

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
    }

    for (int i = 0; i < n; i++) {
        bool a;
        cin >> a;
        on1[i] = a;
    }

    on2 = on1;
    on2[0] = !on2[0];
    on2[1] = !on2[1];

    int cnt1 = 0;
    int cnt2 = 1;

    for (int i = 1; i < n; i++) {
        if (on1[i - 1]) {
            on1[i - 1] = false;
            on1[i] = !on1[i];
            on1[i + 1] = !on1[i + 1];
            cnt1++;
        }
        if (on2[i - 1]) {
            on2[i - 1] = false;
            on2[i] = !on2[i];
            on2[i + 1] = !on2[i + 1];
            cnt2++;
        }
    }

    bool allFalse1 = true;
    bool allFalse2 = true;

    for (int i = 0; i < n; i++) {
        if (on1[i]) {
            allFalse1 = false;
        }
        if (on2[i]) {
            allFalse2 = false;
        }
    }

    if (!allFalse1) {
        cnt1 = INT_MAX;
    }
    if (!allFalse2) {
        cnt2 = INT_MAX;
    }

    int ans = min(cnt1, cnt2);

    if (ans == INT_MAX) {
        cout << "impossible" << endl;
    }
    else {
        cout << ans << endl;
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30