Submission #404405

#	Time	Username	Problem	Language	Result	Execution time	Memory
404405		rama_pang	Alternating Current (BOI18_alternating)	C++17	100 / 100	129 ms	17692 KiB

alternating

#include <bits/stdc++.h>
using namespace std;

class Segment {
 public:
  int N;
  int index;
  int start;
  int length;
  int direction;
  int sortedIndex;
  set<Segment*> children;

  Segment(int _N, int i, int a, int b) {
    N = _N;
    index = i;
    start = a;
    length = (b + N - a) % N + 1;
    direction = 0;
    sortedIndex = -1;
    children.clear();
  }

  bool Include(const Segment &o) {
    int x = (o.start - start + N) % N;
    return x + o.length <= length;
  }

  void SetDirection(int dir) {
    direction = dir;
    for (auto i : children) {
      i->direction = !dir;
    }
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, M;
  cin >> N >> M;

  vector<Segment> segments;
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    segments.emplace_back(Segment(N, i, --a, --b));
  }

  sort(begin(segments), end(segments), [&](const Segment &i, const Segment &j) {
    return i.start < j.start || (i.start == j.start && i.length > j.length);
  });

  for (int i = 0; i < M; i++) {
    segments[i].sortedIndex = i;
  }

  vector<Segment*> mainSegments;
  Segment* last = &segments[0];
  vector<int> inMain(M);
  for (int i_ = 1; i_ < 4 * M; i_++) {
    int i = i_ % M;
    Segment* cur = &segments[i];
    if (cur->index != last->index && last->Include(*cur)) {
      if (inMain[last->index]) {
        last->children.emplace(cur);
      }
    } else {
      last = cur;
      if (i_ >= M && !inMain[cur->index]) {
        inMain[cur->index] = 1;
        mainSegments.emplace_back(cur);
      }
    }
  }

  const auto Alternating = [&](int start_) {
    for (int i_ = 0; i_ < int(mainSegments.size()); i_++) {
      int i = (i_ + start_) % mainSegments.size();
      mainSegments[i]->SetDirection(i_ % 2);
    }
  };

  if (mainSegments.size() % 2 == 0) {
    Alternating(0);
  } else {
    for (int i = 0; i < int(mainSegments.size()); i++) {
      auto S0 = mainSegments[(i + 0) % mainSegments.size()];
      auto S1 = mainSegments[(i + 1) % mainSegments.size()];
      auto S2 = mainSegments[(i + 2) % mainSegments.size()];
      auto S3 = mainSegments[(i + 3) % mainSegments.size()];

      S0->SetDirection(1);
      S1->SetDirection(0);
      S2->SetDirection(0);
      S3->SetDirection(1);

      if ([&]() -> bool {
        // Check if segment S0...S3 is good
        int cur = S0->start;
        int rep = (S3->sortedIndex - S0->sortedIndex + M - 1) % M + 1;
        for (int i_ = 0; i_ < rep; i_++) {
          int i = (S0->sortedIndex + i_) % M;
          if (segments[i].direction == 0) continue;
          int st = segments[i].start;
          if (i < S0->sortedIndex) st += N;
          if (cur < st) return false;
          cur = max(cur, st + segments[i].length);
        }
        int i = S3->sortedIndex;
        int st = segments[i].start;
        if (i <= S0->sortedIndex) st += N;
        if (cur < st) return false;
        return true;
      }()) {
        Alternating((i + 2) % mainSegments.size());
        break;
      }
    }
  }

  if ([&]() -> bool {
    // Check whether solution is valid
    for (int dir = 0; dir < 2; dir++) {
      int cur = 0;
      for (int i = 0; i < 2 * M; i++) if (segments[i % M].direction == dir) {
        int st = segments[i % M].start;
        if (i < M) st -= N;
        if (cur < st) return false;
        cur = max(cur, st + segments[i % M].length);
      }
      if (cur < N) return false;
    }
    return true;
  }()) {
    vector<int> ans(M);
    for (auto seg : segments) {
      ans[seg.index] = seg.direction;
    }
    for (int i = 0; i < M; i++) {
      cout << ans[i];
    }
    cout << '\n';
  } else {
    cout << "impossible\n";
  }
  return 0;
}

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