Submission #1115057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115057		lucascgar	Alternating Current (BOI18_alternating)	C++17	13 / 100	6 ms	3576 KiB

alternating

#include <bits/stdc++.h>
 
using namespace std;
 
/*
 
*/
 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
 
const int MAXN = 1e5+10;
 
vector<int> w[MAXN];
bool ty[MAXN];
pii cy[MAXN];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout << fixed << setprecision(7);
 
    int n, m;
    cin >> n >> m;
  	if (n>20) return 0;
    int a, b;
    for (int i=0;i<m;i++){
        cin >> a >> b;
        cy[i] = {a, b};
    }
    int tg = (1<<m);
    for (int bt=0;bt<tg;bt++){

        for (int i=0;i<m;i++) ty[i] = ((1<<i)&bt);
        bool vl = 1;

        for (int i=1;i<=n;i++){

            bool has[2] = {0,0};

            for (int f=0;f<m;f++){
                a = cy[f].first, b = cy[f].second;
                if ((a<=b && a<=i && b >= i) || (a>b && (a<=i || b>=i))){
                    has[ty[f]]=1;
                }
            }


            if (has[0] != 1 || has[1] != 1){
                vl = 0;
                break;
            }

        }

        if (vl){
            for (int i=0;i<m;i++) cout << (int)ty[i];
            cout << '\n';
            return 0;
        }

    }
 
    cout << "impossible\n";
    return 0;
 
    return 0;
}

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