Submission #1259705

#TimeUsernameProblemLanguageResultExecution timeMemory
1259705SzymonKrzywdaAlternating Current (BOI18_alternating)C++20
32 / 100
22 ms6724 KiB
#include <iostream> #include <vector> using namespace std; #define ff first #define ss second int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<pair<int, int>> seg(m); bool case_a_b = 1; vector<vector<pair<int, int>>> konce(n + 1); for (int i = 0; i < m; i++) { cin >> seg[i].ff >> seg[i].ss; if (seg[i].ff > seg[i].ss) case_a_b = 0; konce[seg[i].ff].push_back({seg[i].ss, i}); } if (case_a_b) { int akt_0 = 0; int akt_1 = 0; vector<int> odp(m, 0); for (int i = 1; i <= n; i++) { sort(konce[i].begin(), konce[i].end()); if (akt_0 + 1 < i || akt_1 + 1 < i) { cout << "impossible\n"; return 0; } if (akt_0 < akt_1) { if (konce[i].size() > 0) { akt_0 = max(akt_0, konce[i].back().first); konce[i].pop_back(); } if (konce[i].size() > 0) { akt_1 = max(akt_1, konce[i].back().first); odp[konce[i].back().second] = 1; konce[i].pop_back(); } } else { if (konce[i].size() > 0) { akt_1 = max(akt_1, konce[i].back().first); odp[konce[i].back().second] = 1; konce[i].pop_back(); } if (konce[i].size() > 0) { akt_0 = max(akt_0, konce[i].back().first); konce[i].pop_back(); } } } if (akt_0 < n || akt_1 < n) { cout << "impossible\n"; return 0; } for (int i = 0; i < m; i++) cout << odp[i]; return 0; } int K = 1 << m; for (int msk = 0; msk < K; msk++) { vector<vector<int>> tab(n + 1, vector<int>(2, 0)); for (int i = 0; i < m; i++) { int bit = 0; if ((1 << i) & msk) bit = 1; int a = seg[i].ff, b = seg[i].ss; if (b < a) { for (int i = a; i <= n; i++) tab[i][bit] = 1; for (int i = 1; i <= b; i++) tab[i][bit] = 1; } else for (int i = a; i <= b; i++) tab[i][bit] = 1; } bool git = 1; for (int i = 1; i <= n; i++) { if (!tab[i][0] || !tab[i][1]) git = 0; } if (git) { for (int i = 0; i < m; i++) { int bit = 0; if ((1 << i) & msk) bit = 1; cout << bit; } return 0; } } cout << "impossible\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...