Submission #1058593

#TimeUsernameProblemLanguageResultExecution timeMemory
1058593otariusAlternating Current (BOI18_alternating)C++17
0 / 100
56 ms15572 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; // #pragma GCC optimize("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define ff first #define sc second #define pb push_back #define ll long long #define pll pair<ll, ll> #define pii pair<int, int> #define ull unsigned long long #define all(x) (x).begin(),(x).end() // #define int long long // #define int unsigned long long // #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> // #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> void open_file(string filename) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } // const ll mod = 1e9 + 7; // const ll mod = 998244353; const ll inf = 1e9; const ll biginf = 1e18; const int maxN = 1e5 + 25; int par[maxN]; vector<int> g[maxN]; void make_set() { for (int i = 0; i <= maxN; i++) par[i] = i; } int find_set(int v) { if (v == par[v]) return v; return par[v] = find_set(par[v]); } void union_set(int x, int y) { x = find_set(x); y = find_set(y); if (x != y) par[y] = x; } struct segtree { int t[4 * maxN], lazy[4 * maxN], n; void init(int _n) { n = _n; for (int i = 0; i < 4 * maxN; i++) t[i] = lazy[i] = 0; } void prop(int v, int tl, int tr) { if (!lazy[v]) return; t[v] += lazy[v]; if (tl != tr) { lazy[2 * v] += lazy[v]; lazy[2 * v + 1] += lazy[v]; } lazy[v] = 0; } void update(int v, int tl, int tr, int l, int r, int val) { prop(v, tl, tr); if (r < tl || tr < l) return; if (l <= tl && tr <= r) { lazy[v] += val; prop(v, tl, tr); return; } int tm = (tl + tr) / 2; update(2 * v, tl, tm, l, r, val); update(2 * v + 1, tm + 1, tr, l, r, val); t[v] = min(t[2 * v], t[2 * v + 1]); } int query(int v, int tl, int tr, int l, int r) { prop(v, tl, tr); if (l > r) return -inf; if (tl == l && tr == r) return t[v]; int tm = (tl + tr) / 2; return min(query(2 * v, tl, tm, l, min(r, tm)), query(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)); } void update(int l, int r, int val) { if (r > n) r -= n; if (l <= r) { update(1, 1, n, l, r, val); } else { update(1, 1, n, l, n, val); update(1, 1, n, 1, r, val); } } int eval() { return query(1, 1, n, 1, n); } } seg[2]; bool check() { return (seg[0].eval() > 0 && seg[1].eval() > 0); } struct line { int x, y, id, cl, clr; line() { } line(int _x, int _y, int _id) { x = _x; y = _y; id = _id; cl = clr = -1; } bool operator<(const line &p) { return make_pair(x, -y) < make_pair(p.x, -p.y); } } arr[maxN]; bool comp(line a, line b) { return a.id < b.id; } vector<line> good; int n, m, mx, mxi, cld[maxN]; void elim() { deque<line> dq; sort(arr + 1, arr + m + 1); for (int i = 1; i <= n; i++) { if (dq.empty() || dq.back().y < arr[i].y) dq.push_back(arr[i]); else cld[arr[i].id] = dq.back().id; } while (dq.size() && dq.front().y <= mx) { cld[dq.front().id] = mxi; dq.pop_front(); } for (line x : dq) good.pb(x); for (int i = 1; i <= m; i++) if (cld[arr[i].id]) arr[i].cl = cld[arr[i].id]; make_set(); for (int i = 1; i <= m; i++) if (arr[i].cl != -1) union_set(arr[i].cl, arr[i].id); for (int i = 1; i <= m; i++) { if (arr[i].cl != -1) { arr[i].cl = find_set(arr[i].id); g[arr[i].cl].pb(arr[i].id); } else g[arr[i].id].pb(arr[i].id); } } void even() { for (int i = 0; i < good.size(); i++) arr[good[i].id].clr = i % 2; for (int i = 1; i <= m; i++) if (arr[i].clr == -1) arr[i].clr = (arr[arr[i].cl].clr ^ 1); for (int i = 1; i <= m; i++) { seg[arr[i].clr].update(arr[i].x, arr[i].y, 1); } if (check()) { for (int i = 1; i <= m; i++) cout << arr[i].clr; } else { cout << "impossible"; } exit(0); } void odd() { for (int i = 0; i < good.size(); i++) arr[good[i].id].clr = i % 2; for (int i = 1; i <= m; i++) if (arr[i].clr == -1) arr[i].clr = (arr[arr[i].cl].clr ^ 1); for (int i = 1; i <= m; i++) seg[arr[i].clr].update(arr[i].x, arr[i].y, 1); if (check()) { for (int i = 1; i <= m; i++) cout << arr[i].clr << ' '; exit(0); } for (int i = 0; i < good.size(); i++) { for (int j : g[good[i].id]) { seg[arr[j].clr].update(arr[j].x, arr[j].y, -1); arr[j].clr ^= 1; seg[arr[j].clr].update(arr[j].x, arr[j].y, 1); } if (check()) { for (int i = 1; i <= m; i++) cout << arr[i].clr << ' '; exit(0); } } cout << "impossible"; exit(0); } void solve() { cin >> n >> m; seg[0].init(n); seg[1].init(n); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; if (l > r) { if (mx < r) { mx = r; mxi = i; } r += n; } arr[i] = {l, r, i}; } elim(); sort(arr + 1, arr + m + 1, comp); sort(all(good), comp); even(); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); cout << '\n'; } return 0; }

Compilation message (stderr)

alternating.cpp: In function 'void even()':
alternating.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < good.size(); i++)
      |                     ~~^~~~~~~~~~~~~
alternating.cpp: In function 'void odd()':
alternating.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = 0; i < good.size(); i++)
      |                     ~~^~~~~~~~~~~~~
alternating.cpp:177:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     } for (int i = 0; i < good.size(); i++) {
      |                       ~~^~~~~~~~~~~~~
alternating.cpp: In function 'void open_file(std::string)':
alternating.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp: In function 'void make_set()':
alternating.cpp:40:44: warning: iteration 100025 invokes undefined behavior [-Waggressive-loop-optimizations]
   40 |     for (int i = 0; i <= maxN; i++) par[i] = i;
      |                                     ~~~~~~~^~~
alternating.cpp:40:23: note: within this loop
   40 |     for (int i = 0; i <= maxN; i++) par[i] = i;
      |                     ~~^~~~~~~
#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...