Submission #536687

#TimeUsernameProblemLanguageResultExecution timeMemory
536687OttoTheDinoAlternating Current (BOI18_alternating)C++17
19 / 100
68 ms16212 KiB
#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; cin >>n >> m; vector<ii> v[2*n]; set<ii> st; set<pair<ii,int>> s; rep (i,0,m-1) { int a, b; cin >> a >> b; a--, b--; if (b<a || a==0) { s.insert({{b,a},i}); } else { v[a].pb({b,i}); } } if (s.size()<2) { cout << "impossible\n"; return 0; } int l = (*s.begin()).fi.fi, x = (*s.begin()).fi.se-1, idl = (*s.begin()).se; if (x==-1) x = n-1; s.erase(s.begin()); int r = (*s.begin()).fi.fi, y = (*s.begin()).fi.se-1, idr = (*s.begin()).se; if (y==-1) y = n-1; s.erase(s.begin()); if (y<x) { swap (l, r); swap (y, x); swap (idl, idr); } bool suc = 1, ans[m+1] = {}; ans[idr] = 1; for (auto sth : s) { st.insert({sth.fi.fi, sth.se}); } rep (i,0,n-1) { for (ii bi : v[i]) st.insert(bi); if (i>l && i<=x) { if (st.size()>1 && (*prev(st.end(),2)).fi>=i) { l = (*prev(st.end(),2)).fi; st.erase(prev(st.end(),2)); } else if (st.size() && (*prev(st.end())).fi>=i) { l = (*prev(st.end())).fi; st.erase(prev(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 (!suc) { cout << "impossible\n"; } else { rep (i,0,m-1) cout << ans[i]; cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...