Submission #234917

#	Time	Username	Problem	Language	Result	Execution time	Memory
234917		anayk	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	41 ms	664 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 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(r-l < 1)
    return r-l+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);
}
 
int 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 l;
  }
 
  int m = (l+r)/2;
  
  int cl = count(l, m, x, group);
  if(cl)
    bs(x, l, m, group);
  else
    bs(x, m+1, r, group);
}
  
void Solve(int N) {
  for(int i = 1; i <= 2*N; i++) {
    for(int j = 0; j < 4; j++) {
      groups[j].push_back(i);
      if(queryRange(0, groups[j].size()-1, j) == groups[j].size()) {
        part[i] = j;
        break;
      }
      else
        groups[j].pop_back();
    }
  }
 
  for(int i = 1; i <= 2*N; i++) {
    for(int j = 0; j < part[i]; j++) {
      int last = 0;
      do {
        last = bs(i, last, groups[j].size()-1, j)+1;
      } while(last < groups[j].size() && Adj[i].size() < 3 && count(last, groups[j].size()-1, i, 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:61:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(queryRange(0, groups[j].size()-1, j) == groups[j].size()) {
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
chameleon.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       } while(last < groups[j].size() && Adj[i].size() < 3 && count(last, groups[j].size()-1, i, j));
               ~~~~~^~~~~~~~~~~~~~~~~~
chameleon.cpp: In function 'int bs(int, int, int, int)':
chameleon.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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