Submission #1259705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259705		SzymonKrzywda	Alternating Current (BOI18_alternating)	C++20	32 / 100	22 ms	6724 KiB

alternating

#include <iostream>
#include <vector>


using namespace std;

#define ff first
#define ss second


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> seg(m);

    bool case_a_b = 1;
    vector<vector<pair<int, int>>> konce(n + 1);

    for (int i = 0; i < m; i++) {
        cin >> seg[i].ff >> seg[i].ss;
        if (seg[i].ff > seg[i].ss) case_a_b = 0;
        konce[seg[i].ff].push_back({seg[i].ss, i});
    }

    if (case_a_b) {
        int akt_0 = 0;
        int akt_1 = 0;
        vector<int> odp(m, 0);
        for (int i = 1; i <= n; i++) {
            sort(konce[i].begin(), konce[i].end());
            if (akt_0 + 1 < i || akt_1 + 1 < i) {
                cout << "impossible\n";
                return 0;
            }

            if (akt_0 < akt_1) {
                if (konce[i].size() > 0) {
                    akt_0 = max(akt_0, konce[i].back().first);
                    konce[i].pop_back();
                }
                if (konce[i].size() > 0) {
                    akt_1 = max(akt_1, konce[i].back().first);
                    odp[konce[i].back().second] = 1;
                    konce[i].pop_back();
                }
            }
            else {
                if (konce[i].size() > 0) {
                    akt_1 = max(akt_1, konce[i].back().first);
                    odp[konce[i].back().second] = 1;
                    konce[i].pop_back();
                }
                
                if (konce[i].size() > 0) {
                    akt_0 = max(akt_0, konce[i].back().first);
                    konce[i].pop_back();
                }
            }
        }

        if (akt_0 < n || akt_1 < n) {
            cout << "impossible\n";
            return 0;
        }

        for (int i = 0; i < m; i++) cout << odp[i];

        return 0;
    }

    int K = 1 << m;
    for (int msk = 0; msk < K; msk++) {
        vector<vector<int>> tab(n + 1, vector<int>(2, 0));
        for (int i = 0; i < m; i++) {
            int bit = 0;
            if ((1 << i) & msk) bit = 1;

            int a = seg[i].ff, b = seg[i].ss;
            
            if (b < a) {
                for (int i = a; i <= n; i++) tab[i][bit] = 1;
                for (int i = 1; i <= b; i++) tab[i][bit] = 1;
            }
            else for (int i = a; i <= b; i++) tab[i][bit] = 1;
        }

        bool git = 1;
        for (int i = 1; i <= n; i++) {
            if (!tab[i][0] || !tab[i][1]) git = 0;
        }
        
        if (git) {
            for (int i = 0; i < m; i++) {
                int bit = 0;
                if ((1 << i) & msk) bit = 1;
                cout << bit;
            }
            return 0;
        }
    }

    cout << "impossible\n";

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26