Submission #212439

#	Time	Username	Problem	Language	Result	Execution time	Memory
212439		IOrtroiii	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	75 ms	760 KiB

chameleon

#include <bits/stdc++.h>

#include "chameleon.h"

using namespace std;

void Solve(int N) {
   vector<vector<int>> adj(2 * N + 1);
   auto hasEdge = [&](int v, vector<int> p) {
      p.emplace_back(v);
      return Query(p) != p.size();
   };
   for (int v = 1; v <= 2 * N; ++v) {
      vector<int> color(2 * N + 1, -1);
      vector<vector<int>> byColor(2);
      function<void(int)> dfs = [&](int v) {
         for (int u : adj[v]) {
            if (color[u] == -1) {
               color[u] = color[v] ^ 1;
               dfs(u);
            }
         }
      };
      for (int i = 1; i < v; ++i) {
         if (color[i] == -1) { color[i] = 0; dfs(i); }
         byColor[color[i]].emplace_back(i);
      }
      for (auto &p : byColor) {
         while (hasEdge(v, p)) {
            int low = 0, high = p.size() - 1;
            while (low < high) {
               int mid = (low + high) >> 1;
               if (hasEdge(v, vector<int>(p.begin(), p.begin() + mid + 1))) {
                  high = mid;
               } else {
                  low = mid + 1;
               }
            }
            adj[v].emplace_back(p[low]);
            adj[p[low]].emplace_back(v);
            p = vector<int>(p.begin() + low + 1, p.end());
         }
      }
   }
   vector<int> prv(2 * N + 1, -1);
   vector<int> nxt(2 * N + 1, -1);
   vector<int> mt(2 * N + 1, -1);
   for (int v = 1; v <= 2 * N; ++v) {
      if (adj[v].size() == 1) {
         mt[v] = adj[v][0];
      } else {
         int u = -1;
         if (Query({v, adj[v][0], adj[v][1]}) == 1) u = adj[v][2];
         if (Query({v, adj[v][1], adj[v][2]}) == 1) u = adj[v][0];
         if (Query({v, adj[v][2], adj[v][0]}) == 1) u = adj[v][1];
         nxt[v] = u; prv[u] = v;
      }
   }
   for (int v = 1; v <= 2 * N; ++v) {
      if (adj[v].size() == 3) {
         mt[v] = adj[v][0] ^ adj[v][1] ^ adj[v][2] ^ prv[v] ^ nxt[v];
      }
      if (v < mt[v]) Answer(v, mt[v]);
   }
}

Compilation message (stderr)

chameleon.cpp: In lambda function:
chameleon.cpp:11:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       return Query(p) != p.size();
              ~~~~~~~~~^~~~~~~~~~~

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