Submission #1259694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259694		SzymonKrzywda	Alternating Current (BOI18_alternating)	C++20	13 / 100	3096 ms	6604 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);

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

    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: 0 / 19
• Subtask 5: 0 / 26