Submission #1034791

#TimeUsernameProblemLanguageResultExecution timeMemory
1034791anangoAlternating Current (BOI18_alternating)C++17
0 / 100
3040 ms6120 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<30; int n,m; vector<pair<int,int>> segments; vector<int> indices,invindices; bool inside(int a, int b, int c) { //is it a,b,c in this order? bool ans = (a<=b && b<=c) || (a<=b && b>c && c<a) || (a>b && b<=c && c<a); ////cout << a <<" " << b <<" " << c <<" " << ans << endl; return ans; } bool between(pair<int,int> s1, pair<int,int> s2) { //is s2 fully between s1's endpoints int a=s1.first; int b = s1.second; int c = s2.first; int d = s2.second; bool ans = inside(a,c,d) && inside(c,d,b) && inside(a,c,b) && inside(a,d,b); ////cout << a <<" " << b <<" " << c <<" " <<d << " " << ans << endl; return ans; } bool works(vector<int> ans) { //1 implies 0-covered, 2 implies 1-covered set<int> remset0; set<int> remset1; for (int i=0; i<n; i++) { remset0.insert(i); remset1.insert(i); } for (int i1=0; i1<m; i1++) { int l = segments[i1].first; int r = segments[i1].second; for (int i=l; i!=r; ) { //cout << "erasing " << i <<" " << l <<" " <<r <<" " << ans[i1] << endl; if (ans[i1]==0 && remset0.count(i)) { remset0.erase(i); } if (ans[i1]==1 && remset1.count(i)) { remset1.erase(i); } i++; i%=n; } if (ans[i1]==0 && remset0.count(r)) { remset0.erase(r); } if (ans[i1]==1 && remset1.count(r)) { remset1.erase(r); } } return (remset0.size()==0) && (remset1.size()==0); } void print_ans(vector<int> answer){ for (int i=0; i<m; i++) { //cout << invindices[i] <<" "; } //cout << endl; for (int i=0; i<m; i++) { cout << answer[invindices[i]]; } cout << endl; } signed main() { #ifndef ONLINE_JUDGE // for getting input from input.txt //freopen("input.txt", "r", stdin); // for writing output to output.txt //freopen("output.txt", "w", stdout); #endif #ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif //fast IO cin >> n >> m; vector<int> answer(m,-1); indices=invindices=vector<int>(m); iota(indices.begin(), indices.end(), (int)0); for (int i=0; i<m; i++) { int s,t; cin >> s >> t; s--; t--; segments.push_back({s,t}); //subtask 4: t>s } stable_sort(indices.begin(), indices.end(), [&](const int i1, const int i2) { return segments[i1]<segments[i2]; }); for (int i=0; i<m; i++) { invindices[indices[i]] = i; } stable_sort(segments.begin(), segments.end()); vector<int> goods; vector<int> covered_by(m,-1); for (int i=0; i<m; i++) { for (int j=0; j<m; j++) { if (j==i) continue; //if i is covered by j if (between(segments[j],segments[i])) { covered_by[i] = j; } } if (covered_by[i]==-1) { goods.push_back(i); } } for (int i=0; i<m; i++) { //cout << i << " " << covered_by[i] << endl; } int k = goods.size(); if (goods.size()%2==0) { for (int i=0; i<k; i++) { //cout << "setting " << goods[i] <<" " << i%2 << endl; answer[goods[i]] = i%2; } for (int i=0; i<m; i++) { if (covered_by[i]!=-1) { //cout << "setting2 " << i <<" " << covered_by[i] <<" " <<answer[covered_by[i]] << endl; answer[i] = 1-answer[covered_by[i]]; } } for (int i=0; i<m; i++) { if (answer[i]!=0 && answer[i]!=1) { answer[i] = 0; } } } else { for (int i=0; i<k; i++) { answer[goods[i]] = i%2; } for (int i=0; i<m; i++) { if (covered_by[i]!=-1) { answer[i] = 1-answer[covered_by[i]]; } } for (int i=0; i<m; i++) { if (answer[i]!=0 && answer[i]!=1) { answer[i] = 0; } } } //cout << "trying answer " << endl; print_ans(answer); if (works(answer)) { print_ans(answer); } else { cout << "impossible" << endl; } }
#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...