Submission #1149487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149487		LucaLucaM	Alternating Current (BOI18_alternating)	C++20	13 / 100	3095 ms	1604 KiB

alternating

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

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

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

  for (int mask = 0; mask < (1 << m); mask++) {
    std::vector<int> color(n, 0);
    for (int i = 0; i < m; i++) {
      auto [l, r] = a[i];
      if (mask >> i & 1) {
        if (l <= r) {
          for (int j = l; j <= r; j++) {
            color[j] |= 1;
          }
        } else {
          for (int j = l; j < n; j++) {
            color[j] |= 1;
          }
          for (int j = 0; j <= r; j++) {
            color[j] |= 1;
          }
        }
      } else {
        if (l <= r) {
          for (int j = l; j <= r; j++) {
            color[j] |= 2;
          }
        } else {
          for (int j = l; j < n; j++) {
            color[j] |= 2;
          }
          for (int j = 0; j <= r; j++) {
            color[j] |= 2;
          }
        }
      }
    }

    bool ok = true;
    for (int i = 0; i < n && ok; i++) {
      if (color[i] != 3) {
        ok = false;
      }
    }

    if (ok) {
      for (int i = 0; i < m; i++) {
        std::cout << (mask >> i & 1);
      }
      return 0;
    }
  }

  std::cout << "impossible";

  return 0;
}

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