oj.uz

Submission #536647

# Submission time Handle Problem Language Result Execution time Memory
536647 2022-03-13T16:24:26 Z OttoTheDino Alternating Current (BOI18_alternating) C++17
19 / 100
 65 ms 11792 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, l = 0, r = 0, x = -1, y = -1; cin >>n >> m;
    vector<ii> v[2*n];
    set<ii> st;
    rep (i,0,m-1) {
        int a, b; cin >> a >> b;
        a--, b--;
        if (b<a) b += n;
        v[a].pb({b,i});
    }
    bool suc = 1, ans[m+1] = {};

    rep (i,0,2*n-1) {
        for (ii bi : v[i]) st.insert(bi);
        if (i>l && i<x) {
            if (st.size() && (*st.rbegin()).fi>=i) {
                l = (*st.rbegin()).fi;
                st.erase(--st.end());
            }
            else {
                suc = 0;
                break;
            }
        }
        if (i>r && i<y) {
            if (st.size() && (*st.rbegin()).fi>=i) {
                ans[(*st.rbegin()).se] = 1;
                r = (*st.rbegin()).fi;
                st.erase(--st.end());
            }
            else {
                suc = 0;
                break;
            }
        }
        if (x==-1) {
            if (st.size()) {
                x = n+i;
                l = (*st.rbegin()).fi;
                st.erase(--st.end());
            }
        }
        if (y==-1) {
            if (st.size()) {
                y = n+i;
                r = (*st.rbegin()).fi;
                ans[(*st.rbegin()).se] = 1;
                st.erase(--st.end());
            }
        }
    }

    if (!suc) {
        cout << "impossible\n";
    }
    else {
        rep (i,0,m-1) cout << ans[i];
        cout << "\n";
    }

    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 324 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 324 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 324 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 10580 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 20 ms 8888 KB Output is correct
4 Correct 25 ms 8908 KB Output is correct
5 Correct 34 ms 7428 KB Output is correct
6 Correct 30 ms 8156 KB Output is correct
7 Correct 33 ms 7720 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 4820 KB Output is correct
10 Correct 42 ms 7456 KB Output is correct
11 Correct 25 ms 7112 KB Output is correct
12 Correct 31 ms 7964 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 61 ms 10652 KB Output is correct
16 Correct 21 ms 8892 KB Output is correct
17 Correct 65 ms 11792 KB Output is correct
18 Correct 59 ms 6688 KB Output is correct
19 Correct 6 ms 5460 KB Output is correct
20 Correct 29 ms 4484 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 324 KB 'impossible' claimed, but there is a solution
6 Halted 0 ms 0 KB -