Submission #1259689

#TimeUsernameProblemLanguageResultExecution timeMemory
1259689patgraAlternating Current (BOI18_alternating)C++20
32 / 100
21 ms3520 KiB
#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"; }
#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...