Submission #251898

#	Time	Username	Problem	Language	Result	Execution time	Memory
251898		jhnah917	Alternating Current (BOI18_alternating)	C++14	32 / 100	198 ms	2152 KiB

alternating

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Info{
    int s, e, x;
    Info() : Info(0, 0, 0) {}
    Info(int s, int e, int x) : s(s), e(e), x(x) {}
    bool operator < (const Info &t) const {
        if(s != t.s) return s < t.s;
        if(e != t.e) return e > t.e;
        return x < t.x;
    }
};

int n, m;
Info a[101010];
int ans[101010];
bool chk[101010][2];

void naive(){
    for(int bit=0; bit<(1 << m); bit++){
        memset(chk, 0, sizeof chk);
        for(int i=1; i<=m; i++){
            for(int k=a[i].s; ; k++){
                if(k > n) k = 1;
                chk[k][bit >> i-1 & 1] = 1;
                if(k == a[i].e) break;
            }
        }
        int flag = 1;
        for(int i=1; i<=n; i++) flag &= (chk[i][0] & chk[i][1]);
        if(flag){
            for(int i=0; i<m; i++) cout << (bit >> i & 1);
            return;
        }
    }
    cout << "impossible";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=m; i++){ cin >> a[i].s >> a[i].e; a[i].x = i; }
    if(n <= 15 && m <= 15){ naive(); return 0; }
    sort(a+1, a+m+1);
    int cnt0 = 0, cnt1 = 0;
    for(int i=1; i<=m; i++){
        int s = a[i].s, e = a[i].e, x = a[i].x;
        if(cnt0 < cnt1){
            if(cnt0 >= s-1) cnt0 = max(cnt0, e), ans[x] = 0;
        }else{
            if(cnt1 >= s-1) cnt1 = max(cnt1, e), ans[x] = 1;
        }
    }
    if(cnt0 < n || cnt1 < n){
        cout << "impossible"; return 0;
    }
    for(int i=1; i<=m; i++) cout << ans[i];
}

Compilation message (stderr)

alternating.cpp: In function 'void naive()':
alternating.cpp:32:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
                 chk[k][bit >> i-1 & 1] = 1;
                               ~^~

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