Submission #1113627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113627		ortsac	Alternating Current (BOI18_alternating)	C++17	19 / 100	64 ms	6764 KiB

alternating

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second
#define t(i) ((int) s[i].size())

const int MAXN = 1e5 + 10;
vector<pii> s[MAXN];

int32_t main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        s[a].push_back({b, i});
    }
    for (int i = 1; i <= n; i++) {
        sort(s[i].begin(), s[i].end());
        reverse(s[i].begin(), s[i].end());
        while (t(i) > 2) s[i].pop_back();
    }
    vector<int> ans(m);
    int zTill = -1, oTill = -1;
    for (int i = 1; i <= n; i++) {
        int need = 0;
        if (zTill < i) {
            zTill = -1;
            need++;
        }
        if (oTill < i) {
            oTill = -1;
            need++;
        }
        if (need > t(i)) {
            cout << "impossible\n";
            return 0;
        }
        if (t(i) == 1) {
            if (oTill <= zTill) {
                oTill = max(oTill, s[i][0].fr);
                ans[s[i][0].se] = 0;
            } else {
                zTill = max(zTill, s[i][0].fr);
                ans[s[i][0].se] = 1;
            }
        } else if (t(i) == 2) {
            if (oTill <= zTill) {
                oTill = max(oTill, s[i][0].fr);
                ans[s[i][0].se] = 0;
                zTill = max(zTill, s[i][1].fr);
                ans[s[i][1].se] = 1;
            } else {
                zTill = max(zTill, s[i][0].fr);
                ans[s[i][0].se] = 1;
                oTill = max(oTill, s[i][1].fr);
                ans[s[i][1].se] = 0;
            }
        }
    }
    for (auto u : ans) cout << u;
    cout << "\n";
}

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