Submission #234857

#	Time	Username	Problem	Language	Result	Execution time	Memory
234857		anayk	Chameleon's Love (JOI20_chameleon)	C++14	40 / 100	51 ms	504 KiB

chameleon

#include "chameleon.h"
#include <set>
#include <vector>

std::set<int> Adj[1001];
std::vector<int> edges[1001];
std::vector<int> groups[4];
int part[1001];

int check(int x, int y) {
  return (y != x + 1);
}

int threeQuery(int x, int y, int z) {
  std::vector<int> q;
  q.push_back(x);
  q.push_back(y);
  q.push_back(z);
  return Query(q);
}

int queryRange(int l, int r, int group) {
  if(l == r)
    return 1;

  std::vector<int> q;
  for(int i = l; i <= r; i++)
    q.push_back(groups[group][i]);

  return Query(q);
}

int queryRange(int l, int r, int x, int group) {
  std::vector<int> q;
  for(int i = l; i <= r; i++)
    q.push_back(groups[group][i]);
  q.push_back(x);
  return Query(q);
}

void bs(int x, int l, int r, int group) {
  if(l == r) {
    Adj[x].insert(groups[group][l]);
    Adj[groups[group][l]].insert(x);
    return;
  }

  int m = (l+r)/2;
  if(check(queryRange(l, m, group), queryRange(l, m, x, group)))
    bs(x, l, m, group);
  if(check(queryRange(m+1, r, group), queryRange(m+1, r, x, group)))
    bs(x, m+1, r, group);
}
  
void Solve(int N) {
  for(int i = 0; i < 4; i++) {
    groups[i].push_back(i+1);
    part[i+1] = i;
  }

  for(int i = 5; i <= 2*N; i++) {
    for(int j = 0; j < 4; j++) {
      groups[j].push_back(i);
      if(Query(groups[j]) == groups[j].size()) {
        part[i] = j;
        break;
      }
      else
        groups[j].pop_back();
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    for(int j = part[i]+1; j < 4; j++) {
      if(check(queryRange(0, groups[j].size()-1, j), queryRange(0, groups[j].size()-1, i, j)))
        bs(i, 0, groups[j].size()-1, j);
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    if(Adj[i].size() == 3) {
      for(std::set<int>::iterator it = Adj[i].begin(); it != Adj[i].end(); it++) {
        edges[i].push_back(*it);
      }
    }
  }
  
  for(int i = 1; i <= 2*N; i++) {
    if(edges[i].size() == 3) {
      int x0 = threeQuery(i, edges[i][1], edges[i][2]);
      int x1 = threeQuery(i, edges[i][0], edges[i][2]);

      int x;
      if(x0 == 1)
        x = edges[i][0];
      else if(x1 == 1)
        x = edges[i][1];
      else
        x = edges[i][2];

      Adj[x].erase(i);
      Adj[i].erase(x);
    }
  }

  for(int i = 1; i <= 2*N; i++) {
    int j = *Adj[i].begin();
    if(i < j)
      Answer(i, j);
  }
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(Query(groups[j]) == groups[j].size()) {
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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