Submission #1039472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039472		juicy	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	33 ms	612 KiB

chameleon

// https://codeforces.com/blog/entry/74871?#comment-591244

#include <bits/stdc++.h>

#include "chameleon.h"

using namespace std;

namespace {
  ostream &operator << (ostream &os, vector<int> v) {
    for (int i = 0; i < v.size(); ++i) {
      os << (i ? ", " : "") << i;
    }
    return os;
  }

  void __print() {
    cerr << "]\n";
  }

  template<class T, class... V>
  void __print(T t, V... v) {
    cerr << t;
    if (sizeof...(v)) {
      cerr << ", ";
    }
    __print(v...);
  }

  #define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
}

void Solve(int N) {
  vector<vector<int>> g(2 * N);
  auto add = [&](int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  };
  vector<int> c(2 * N, -1);
  auto dfs = [&](auto dfs, int u) -> void {
    for (int v : g[u]) {
      if (c[v] == -1) {
        c[v] = c[u] ^ 1;
        dfs(dfs, v);
      } else {
        assert(c[v] == 1 - c[u]);
      }
    }
  };  
  array<vector<int>, 2> cands;
  auto color = [&](int p) {
    fill(c.begin(), c.end(), -1);
    for (auto it : {0, 1}) {
      cands[it].clear();
    }
    for (int i = 0; i < p; ++i) {
      if (c[i] == -1) {
        c[i] = 0;
        dfs(dfs, i);
      }
      cands[c[i]].push_back(i + 1);
    }
  };
  auto check = [&](vector<int> v, int p) {
    v.push_back(p + 1);
    assert(v.size() > 1);
    return Query(v) != v.size();
  };
  for (int i = 1; i < 2 * N; ++i) {
    color(i);
    for (auto it : {0, 1}) {
      while (cands[it].size() && check(cands[it], i)) {
        int L = 0, R = cands[it].size() - 1, p = -1;
        while (L <= R) {
          int md = (L + R) / 2;
          if (check(vector<int>(cands[it].begin(), cands[it].begin() + md + 1), i)) {
            p = md;
            R = md - 1;
          } else {
            L = md + 1;
          }
        }
        assert(~p);
        add(i, cands[it][p] - 1);
        cands[it] = vector<int>(cands[it].begin() + p + 1, cands[it].end());
      }
    }
  }
  auto nxt = [&](int x, int y) {
    if ((x += y) >= 3) {
      x -= 3;
    }
    if (x < 0) {
      x += 3;
    }
    return x;
  };
  vector<int> res(2 * N);
  for (int i = 0; i < 2 * N; ++i) {
    for (int x : g[i]) {
      res[i] += x;
    }
    if (g[i].size() == 3) {
      for (int j = 0; j < 3; ++j) {
        if (Query({i + 1, g[i][j] + 1, g[i][nxt(j, 1)] + 1}) == 1) {
          int p = g[i][nxt(j, -1)];
          res[i] -= p;
          res[p] -= i;
        }
      }
    }
  }
  for (int i = 0; i < 2 * N; ++i) {
    if (i < res[i]) {
      Answer(i + 1, res[i] + 1);
    }
  }
}

Compilation message (stderr)

chameleon.cpp: In function 'std::ostream& {anonymous}::operator<<(std::ostream&, std::vector<int>)':
chameleon.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~
chameleon.cpp: In lambda function:
chameleon.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     return Query(v) != v.size();
      |            ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: At global scope:
chameleon.cpp:17:8: warning: 'void {anonymous}::__print()' defined but not used [-Wunused-function]
   17 |   void __print() {
      |        ^~~~~~~
chameleon.cpp:10:12: warning: 'std::ostream& {anonymous}::operator<<(std::ostream&, std::vector<int>)' defined but not used [-Wunused-function]
   10 |   ostream &operator << (ostream &os, vector<int> v) {
      |            ^~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36