Submission #234887

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

chameleon

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

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

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);
}

int count(int l, int r, int x, int group) {
  return (r-l+2) - queryRange(l, r, x, group);
}

void bs(int x, int l, int r, int group, int c) {
  //if(x == 8 || x == 7) {
  //  std::cout << x << " " << l << " " << r << " " << c << " " << group << std::endl;
  //}
  if(c == 0)
    return;
  
  if(l == r) {
    //std::cout << x << " " << groups[group][l] << std::endl;
    Adj[x].insert(groups[group][l]);
    Adj[groups[group][l]].insert(x);
    return;
  }

  int m = (l+r)/2;
  
  int cl = count(l, m, x, group);
  bs(x, l, m, group, cl);
  if(Adj[x].size() == 3)
    return;
  bs(x, m+1, r, group, cl == 0 ? c : count(m+1, r, x, group));
  //if(c == 1) {
  //  if(count(l, m, x, group))
  //    bs(x, l, m, group, 1);
  //  else
  //    bs(x, m+1, r, group, 1);
  //}
  //else {
  //  int cl = count(l, m, x, group);
  //  bs(x, l, m, group, cl);

  //  if(cl <= 1)
  //    bs(x, m+1, r, group, 2);
  //  else {
  //    bs(x, m+1, r, group, count(m+1, r, x, 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();
    }
  }

  //std::cout << "groups" << std::endl;
  //for(int i = 0; i < 4; i++) {
  //        for(int j : groups[i])
  //      	  std::cout << j << " ";
  //        std::cout << std::endl;
  //}

  for(int i = 1; i <= 2*N; i++) {
    for(int j = part[i]+1; j < 4; j++) {
      if(Adj[i].size() == 3)
        break;
      int c = count(0, groups[j].size()-1, i, j);
      //std::cout << i << " " << j << " " << c << std::endl;
      bs(i, 0, groups[j].size()-1, j, c);
    }
  }

  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:90:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(Query(groups[j]) == groups[j].size()) {
          ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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