Submission #1259707

#TimeUsernameProblemLanguageResultExecution timeMemory
1259707Zbyszek99Alternating Current (BOI18_alternating)C++20
0 / 100
3094 ms27836 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vector<pii> segs; int m,n; vi graph[1001*1001]; bool odw[1001*1001]; int prev_[1001*1001]; int rel_ind[1001]; void dfs(int v, int pop) { prev_[v] = pop; odw[v] = 1; forall(it,graph[v]) { if(!odw[it]) dfs(it,v); } } bool ans[1001]; void calc(int s1, int s2) { rep(i,n*2) { odw[i] = 0; prev_[i] = -1; graph[i] = {}; } rep(i,n) { rep(j,n) { if(i == j) continue; int v = i+n*j; rep(k,n) { if(k == i || k == j) continue; if((segs[i].ss <= segs[j].ss || segs[j].ss < segs[j].ff) && segs[i].ff <= segs[i].ss && segs[k].ff <= segs[i].ss+1 && (segs[k].ss > segs[i].ss || segs[k].ff > segs[k].ss)) { graph[v].pb(k+n*j); } if((segs[i].ss >= segs[j].ss || segs[i].ss < segs[i].ff) && segs[j].ff <= segs[j].ss && segs[k].ff <= segs[j].ss+1 && (segs[k].ss > segs[j].ss || segs[k].ff > segs[k].ss)) { graph[v].pb(i+n*k); } } } } dfs(s1+s2*n,-1); rep(i,n) { rep(j,n) { if(segs[i].ff > segs[i].ss || (segs[i].ss == m && segs[s1].ff == 1)) if(segs[j].ff > segs[j].ss || (segs[j].ss == m && segs[s2].ff == 1)) { if((segs[i].ss >= segs[s1].ff-1 || (i == s1)) && (segs[j].ss >= segs[s2].ff-1 || j == s2) && odw[i+n*j] && (i != s1 || segs[s1].ff == (segs[s1].ss+1)%n) && (j != s2 || segs[s2].ff == (segs[s2].ss+1)%n) && j != s1 && i != s2) { vi path; int cur = i+n*j; ans[rel_ind[s1]] = 0; ans[rel_ind[s2]] = 1; while(true) { if(prev_[cur] == -1 || prev_[cur] == 0) break; ans[rel_ind[cur%n]] = 0; ans[rel_ind[cur/n]] = 1; cur = prev_[cur]; } rep(i,n) cout << ans[i]; cout << "\n"; exit(0); } } } } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); cin >> m >> n; vector<pair<int,pii>> segs2; rep(i,n) { int a,b; cin >> a >> b; segs2.pb({a,{b,i}}); } sort(all(segs2)); rep(i,n) { rel_ind[i] = segs2[i].ss.ss; segs.pb({segs2[i].ff,segs2[i].ss.ff}); } calc(0,1); if(siz(segs) > 2) calc(0,2); if(siz(segs) > 3) calc(0,3); if(siz(segs) > 4) calc(0,4); 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...