Submission #1149521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149521		LucaLucaM	Alternating Current (BOI18_alternating)	C++20	33 / 100	2202 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 = 1000;

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;
      }
    }
  }
}

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<int>> active(n);

  for (int i = 0; i < m; i++) {
    auto [l, r] = a[i];
    if (l <= r) { 
      for (int j = l; j <= r; j++) {
        active[j].push_back(i);
      }
    } else {
      for (int j = l; j < n; j++) {
        active[j].push_back(i);
      }
      for (int j = 0; j <= r; j++) {
        active[j].push_back(i);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    if ((int) active[i].size() <= 1) {
      std::cout << "impossible";
      return 0;
    } else if ((int) active[i].size() == 2) {
      add_edge(active[i][0], active[i][1]);
    }
  }

  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);
      std::set<int> st[2];

      auto add_colored = [&](int l, int r, int c) {
        if (l <= r) {
          for (int i = l; i <= r; i++) {
            taken[i] |= (1 << c);
          }
        } else {
          for (int i = l; i < n; i++) {
            taken[i] |= (1 << c);
          }
          for (int i = 0; i <= r; i++) {
            taken[i] |= (1 << c);
          }
        }
      };
      // std::shuffle(order.begin(), order.end(), rng);
      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];
          int become = 0;
          if (l <= r) {
            for (int j = l; j <= r; j++) {
              become |= (3 ^ taken[j]);
            }
          } else {
            for (int j = l; j < n; j++) {
              become |= (3 ^ taken[j]);
            }
            for (int j = 0; j <= r; j++) {
              become |= (3 ^ taken[j]);
            }
          }
          if (become & 1) {
            color[i] = 0;
          } else {
            color[i] = 1;
          }
          add_colored(l, r, color[i]);
        }
      }
      for (int i = 0; i < m; i++) {
        std::cout << color[i];
      }
      return 0;
    }
  }
  
  return 0;
}

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