Submission #1210864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210864		abczz	Chameleon's Love (JOI20_chameleon)	C++20	64 / 100	31 ms	504 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <iostream>
#include <map>
#define ll int

using namespace std;

void Solve(int N) {
  map <ll, ll> mp[2*N+1];
  bool done[2*N+1];
  ll A[2*N+1], B[2*N+1];
  vector <ll> V[4], U, tmp;
  for (int i=1; i<=2*N; ++i) {
    A[i] = B[i] = -1;
    done[i] = 0;
    U.push_back(i);
  }
  for (int i=0; i<4; ++i) {
    tmp.clear();
    for (int j=0; j<U.size(); ++j) {
      V[i].push_back(U[j]);
      if (V[i].size() == 1) continue;
      else if (Query(V[i]) != V[i].size()) {
        tmp.push_back(U[j]);
        V[i].pop_back();
      }
    }
    swap(U, tmp);
  }
  for (int i=1; i<=2*N; ++i) {
    for (int j=0; j<4; ++j) {
      while (true) {
        bool ok = 1;
        tmp.clear();
        for (auto u : V[j]) {
          if (u == i) ok = 0;
          else if (!mp[i].count(u)) tmp.push_back(u);
        }
        if (ok) {
          tmp.push_back(i);
          if (tmp.size() == 1 || Query(tmp) == tmp.size()) break;
          ll l = 0, r = tmp.size()-1, mid;
          while (l < r) {
            mid = (l+r)/2;
            U.clear();
            for (int j=l; j<=mid; ++j) {
              U.push_back(tmp[j]);
            }
            U.push_back(i);
            if (Query(U) == U.size()) l = mid+1;
            else r = mid;
          }
          ++mp[i][tmp[l]];
          ++mp[tmp[l]][i];
          swap(tmp[l], tmp[tmp.size()-1]);
          tmp.pop_back();
        }
        else break;
      }
    }
  }
  for (int i=1; i<=2*N; ++i) {
    tmp.clear();
    for (auto [x, y] : mp[i]) {
      tmp.push_back(x);
    }
    if (tmp.size() == 3) {
      bool ok = 0;
      for (int j=0; j<2; ++j) {
        U = {tmp[j], tmp[(j+1)%3], i};
        if (Query(U) == 1) {
          ok = 1;
          A[i] = tmp[(j+2)%3];
          B[tmp[(j+2)%3]] = i;
          break;
        }
      }
      if (!ok) A[i] = tmp[1], B[tmp[1]] = i;
    }
  }
  for (int i=1; i<=2*N; ++i) {
    if (done[i]) continue;
    for (auto [x, y] : mp[i]) {
      if (x == A[i] || x == B[i]) continue;
      Answer(i, x);
      done[i] = done[x] = 1;
      break;
    }
  }
}

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