Submission #1259689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259689		patgra	Alternating Current (BOI18_alternating)	C++20	32 / 100	21 ms	3520 KiB

alternating

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    bool noround = true;
    vector<pair<int, int>> v;
    int a, b;
    rep(i, 0, m) {
        cin >> a >> b;
        if(a > b) noround = false;
        v.pb({a, b});
    }

    if(noround) {
        vector<pair<pair<int, int>, int>> v2;
        rep(i, 0, m) v2.pb({v[i], i});
        ranges::sort(v2);
        a = 0, b = 0;
        vector<bool> ans(m);
        repIn2(lr, i, v2) {
            auto [l, r] = lr;
            if(a < b) {
                if(l - 1 > a) { cout << "impossible\n"; return 0; }
                a = max(a, r);
            }
            else {
                if(l - 1 > b) { cout << "impossible\n"; return 0; }
                b = max(b, r);
                ans[i] = 1;
            }
        }
        if(a < n || b < n) { cout << "impossible\n"; return 0; }
        rep(i, 0, m) cout << ans[i];
        cout << '\n';
        return 0;
    }

    rep(mask, 0, 1 << m) {
        vector<bool> a(n), b(n);
        rep(i, 0, m) {
            rep(j, v[i].first, v[i].second) {
                (mask & (1 << i) ? a : b)[j - 1] = true;
                if(j == n) j -= n;
            }
            (mask & (1 << i) ? a : b)[v[i].second - 1] = true;
        }
        bool g = true;
        rep(i, 0, n) g = g && a[i] && b[i];
        if(g) {
            rep(i, 0, m) cout << ((mask >> i) & 1);
            cout << '\n';
            return 0;
        }
    }
    cout << "impossible\n";

}

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