Submission #1149533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149533		LucaLucaM	Alternating Current (BOI18_alternating)	C++20	0 / 100	757 ms	1114112 KiB

alternating

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <random>
#include <set>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 1e5;

std::vector<int> g[NMAX];
bool vis[NMAX];
bool color[NMAX];

void add_edge(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u);
}

bool bipartite = true;

void dfs(int u) {
  vis[u] = true;
  for (const auto &v : g[u]) {
    if (!vis[v]) {
      color[v] = 1 ^ color[u];
      dfs(v);
    } else {
      if (color[u] == color[v]) {
        bipartite = false;
      }
    }
  }
}

int p[2][NMAX];

int root(int c, int u) {
  return p[c][u] == u? u : p[c][u] = root(c, p[c][p[c][u]]);
}
void activate(int c, int u) {
  p[c][u] = p[c][u + 1];
}

struct Event {
  int index;
  bool add;
  bool operator < (const Event &other) const {
    return add < other.add;
  };
}; 

std::mt19937 rng(123);

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n, m;
  std::cin >> n >> m;

  std::vector<std::pair<int, int>> a(m);
  for (auto &[l, r] : a) {
    std::cin >> l >> r;
    l--, r--;
  }

  std::vector<std::vector<Event>> sweep(n + 1);
  
  for (int i = 0; i < m; i++) {
    auto [l, r] = a[i];
    if (l <= r) { 
      sweep[l].push_back({i, true});
      sweep[r + 1].push_back({i, false});
    } else {
      sweep[0].push_back({i, true});
      sweep[r + 1].push_back({i, false});
      sweep[l].push_back({i, true});
    }
  }

  std::set<int> active;

  for (int i = 0; i < n; i++) {
    for (const auto &event : sweep[i]) {
      if (event.add) {
        active.insert(event.index);
      } else {
        active.erase(event.index);
      }
    }
    if ((int) active.size() <= 1) {
      std::cout << "impossible";
      return 0;
    } else if ((int) active.size() == 2) {
      add_edge(*active.begin(), *active.rbegin());
    }
  }

  for (int i = 0; i < m; i++) {
    if (!vis[i] && !g[i].empty()) {
      dfs(i);
    }
  }

  if (!bipartite) {
    std::cout << "impossible";
  } else {
    std::vector<int> order(m);
    for (int i = 0; i < m; i++) {
      order[i] = i;
    }
    for (int repeat = 0; repeat < 1; repeat++) {
      std::vector<int> taken(n, 0);
      for (int i = 0; i <= n; i++) {
        p[0][i] = p[1][i] = i;
      }
      
      auto add_seg = [&](int l, int r, int c) {
        int p = root(c, l);
        while (p <= r) {
          activate(c, p);
          p = root(c, p);
        }
      };
      auto add_colored = [&](int l, int r, int c) {
        if (l <= r) {
          add_seg(l, r, c);  
        } else {
          add_seg(0, r, c);
          add_seg(l, n - 1, c);
        }
      };
      auto is_colored = [&](int l, int r, int c) {
        if (l <= r) {
          return root(c, l) > r;
        } else {
          return root(c, l) == n || root(c, 0) > r;
        }
      };


      for (int i = 0; i < m; i++) {
        if (vis[i]) {
          add_colored(a[i].first, a[i].second, color[i]);
        }
      }
      for (const auto &i : order) {
        if (!vis[i]) {
          auto [l, r] = a[i];
          if (!is_colored(l, r, 0)) {
            color[i] = 0;
          } else {
            color[i] = 1;
          }
          add_colored(l, r, color[i]);
        }
      } 
      bool ok = true;
      for (int i = 0; i < n; i++) {
        if (root(0, i) == i || root(1, i) == i) {
          ok = false;
        }
      }
      if (ok) {
        for (int i = 0; i < m; i++) {
          std::cout << color[i];
        }
        return 0;
      }
      
      std::shuffle(order.begin(), order.end(), rng);
    }
    
    // assert(false);
  }
  
  return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 19
• Subtask 5: 0 / 26