Submission #944657

#	Time	Username	Problem	Language	Result	Execution time	Memory
944657		WongYiKai	Chameleon's Love (JOI20_chameleon)	C++14	44 / 100	31 ms	732 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef int ll;

void solve2(int N) {
  
  vector<ll> pa[2*N+5];
  for (int i=1;i<=2*N;i++){
	  for (int j=i+1;j<=2*N;j++){
		  vector<ll> temp(2);
		  temp[0] = i;
		  temp[1] = j;
		  if (Query(temp)==1) {
			  pa[i].push_back(j);
			  pa[j].push_back(i);
		  }
	  }
  }
  ll col[2*N+5];
  ll know[2*N+5];
  memset(know,0,sizeof(know));
  for (int i=1;i<=2*N;i++){
	  if (know[i]==1) continue;
	  if (pa[i].size()==1){
		  col[i] = pa[i][0];
		  col[pa[i][0]] = i;
		  know[i] = 1;
		  know[pa[i][0]] = 1;
		  continue;
	  }
	  ll like=-1;
	  vector<ll> temp(3);
	  temp[0] = i;
	  temp[1] = pa[i][0];
	  temp[2] = pa[i][1];
	  if (Query(temp)==1){
		  like = 2;
	  }
	  temp[1] = pa[i][1];
	  temp[2] = pa[i][2];
	  if (Query(temp)==1){
		  like = 0;
	  }
	  temp[1] = pa[i][2];
	  temp[2] = pa[i][0];
	  if (Query(temp)==1){
		  like = 1;
	  }
	  //cout << i << " " << pa[i][like] << "\n";
	  ll fail=-1,pass=-1;
	  for (int j=0;j<3;j++){
		  if (j==like) continue;
		  ll x = pa[i][j];
		  if (know[x]==1) {
			  fail=j;
			  break;
		  }
		  if (pa[x].size()==1){
			  if (pa[x][0]==i){
				  pass=j;
				  break;
			  }
			  else{
				  fail=j;
				  break;
			  }
		  }
		  ll like2=-1;
		  vector<ll> temp2(3);
		  temp2[0] = x;
		  temp2[1] = pa[x][0];
		  temp2[2] = pa[x][1];
		  if (Query(temp2)==1){
			  like2 = 2;
		  }
		  temp2[1] = pa[x][1];
		  temp2[2] = pa[x][2];
		  if (Query(temp2)==1){
			  like2 = 0;
		  }
		  temp2[1] = pa[x][2];
		  temp2[2] = pa[x][0];
		  if (Query(temp2)==1){
			  like2 = 1;
		  }
		  //cout << x << " " << pa[x][like2] << "\n";
		  if (pa[x][like2]==i){
			  fail=j;
			  break;
		  }
		  else{
			  pass=j;
			  break;
		  }
	  }
	  //cout << i << " " << fail << " " << pass << "\n";
	  if (fail==-1){
		  col[i] = pa[i][pass];
		  col[pa[i][pass]] = i;
		  know[i] = 1;
		  know[pa[i][pass]] = 1;
	  }
	  else{
		  for (int j=0;j<3;j++){
			  if (j==like || j==fail) continue;
			  col[i] = pa[i][j];
			  col[pa[i][j]] = i;
			  know[i] = 1;
			  know[pa[i][j]] = 1;
		  }
	  }
  }
  ll out[2*N+5];
  memset(out,0,sizeof(out));
  for (int i = 1; i <= 2*N; i++) {
	  if (out[i]==1) continue;
	  //cout << i << " " << col[i] << "\n";
	  Answer(i,col[i]);
	  out[i]=1;
	  out[col[i]]=1;
  }
}
 
void Solve(int N) {
  if (N<=50) {
	  solve2(N);
  }
  else{
	  /*
	  vector<ll> g1,g2,nt;
	  for (int i=2;i<=2*N;i++){
		  nt.push(i);
	  }
	  g1.push(1);
	  ll l=1,r=nt.size();
	  while (l<r){
		  ll m = l+(r-l)/2;
		  vector<ll> temp;
		  temp.push_back(i);
		  for (int k=l;k<=m;k++){
			  if (find(used.begin(),used.end(),nt[k])!=used.end()) continue;
			  temp.push_back(nt[k]);
		  }
		  if (Query(temp)!=temp.size()){
			  r=m;
		  }
		  else{
			  l=m+1;
		  }
		  temp.clear();
	  }
	  */
	  
	  ll found[2*N+5];
	  memset(found,0,sizeof(found));
	  vector<ll> pa[2*N+5];
	  for (int i=1;i<2*N;i++){
		  if (found[i]==1) continue;
		  vector<ll> used;
		  for (int j=0;j<3;j++){
			  if (j!=used.size()) continue;
			  ll l=i+1,r=2*N;
			  while (l<r){
				  ll m = l+(r-l)/2;
				  vector<ll> temp,temp2;
				  temp.push_back(i);
				  for (int k=l;k<=m;k++){
					  if (find(used.begin(),used.end(),k)!=used.end()) continue;
					  temp.push_back(k);
					  temp2.push_back(k);
				  }
				  ll q1 = Query(temp);
				  if (q1!=temp.size()){
					  if (Query(temp2)==q1) r=m;
					  else l=m+1;
				  }
				  else{
					  l=m+1;
				  }
				  temp.clear();
				  temp2.clear();
			  }
			  vector<ll> tem;
			  tem.push_back(l);
			  tem.push_back(i);
			  if (find(used.begin(),used.end(),l)!=used.end() || Query(tem)==2) continue;
			  //cout << i << " " << l << "\n";
			  pa[i].push_back(l);
			  pa[l].push_back(i);
			  used.push_back(l);
		  }
		  if (used.size()==1) {
			  found[i]=1;
			  found[used[0]]=1;
		  }
	  }
	  /*
	  for (int i=1;i<=2*N;i++){
		  cout << i << ": ";
		  for (auto item:pa[i]) cout << item << " ";
		  cout << "\n";
		  cout << i << ": " << found[i] << "\n";
	  }
	  cout << "\n";
	  */
	  //for (auto item:pa[1]) cout << item << " ";
	  //cout << "\n";
	  
	  /*
	  vector<ll> pa[2*N+5];
	  for (int i=1;i<=N;i++){
		  vector<ll> used;
		  for (int j=0;j<3;j++){
			  ll l=N+1,r=2*N;
			  while (l<r){
				  ll m = l+(r-l)/2;
				  vector<ll> temp;
				  temp.push_back(i);
				  for (int k=l;k<=m;k++){
					  if (find(used.begin(),used.end(),k)!=used.end()) continue;
					  temp.push_back(k);
				  }
				  if (Query(temp)!=temp.size()){
					  r=m;
				  }
				  else{
					  l=m+1;
				  }
				  temp.clear();
			  }
			  vector<ll> tem;
			  tem.push_back(l);
			  tem.push_back(i);
			  if (find(used.begin(),used.end(),l)!=used.end() || Query(tem)==2) continue;
			  //cout << i << " " << l << "\n";
			  pa[i].push_back(l);
			  pa[l].push_back(i);
			  used.push_back(l);
		  }
	  }
	  */
	  //cout << "a";
	  ll col[2*N+5];
	  ll know[2*N+5];
	  memset(know,0,sizeof(know));
	  for (int i=1;i<=2*N;i++){
		  //cout << i << ": ";
		  //for (auto item:pa[i]) cout << item << " ";
		  //cout << "\n";
		  if (know[i]==1) continue;
		  if (pa[i].size()==1){
			  col[i] = pa[i][0];
			  col[pa[i][0]] = i;
			  know[i] = 1;
			  know[pa[i][0]] = 1;
			  continue;
		  }
		  ll like=-1;
		  vector<ll> temp(3);
		  temp[0] = i;
		  temp[1] = pa[i][0];
		  temp[2] = pa[i][1];
		  if (Query(temp)==1){
			  like = 2;
		  }
		  temp[1] = pa[i][1];
		  temp[2] = pa[i][2];
		  if (Query(temp)==1){
			  like = 0;
		  }
		  temp[1] = pa[i][2];
		  temp[2] = pa[i][0];
		  if (Query(temp)==1){
			  like = 1;
		  }
		  //cout << i << " " << pa[i][like] << "\n";
		  ll fail=-1,pass=-1;
		  for (int j=0;j<3;j++){
			  if (j==like) continue;
			  ll x = pa[i][j];
			  if (know[x]==1) {
				  fail=j;
				  break;
			  }
			  if (pa[x].size()==1){
				  if (pa[x][0]==i){
					  pass=j;
					  break;
				  }
				  else{
					  fail=j;
					  break;
				  }
			  }
			  ll like2=-1;
			  vector<ll> temp2(3);
			  temp2[0] = x;
			  temp2[1] = pa[x][0];
			  temp2[2] = pa[x][1];
			  if (Query(temp2)==1){
				  like2 = 2;
			  }
			  temp2[1] = pa[x][1];
			  temp2[2] = pa[x][2];
			  if (Query(temp2)==1){
				  like2 = 0;
			  }
			  temp2[1] = pa[x][2];
			  temp2[2] = pa[x][0];
			  if (Query(temp2)==1){
				  like2 = 1;
			  }
			  //cout << x << " " << pa[x][like2] << "\n";
			  if (pa[x][like2]==i){
				  fail=j;
				  break;
			  }
			  else{
				  pass=j;
				  break;
			  }
		  }
		  //cout << i << " " << fail << " " << pass << "\n";
		  if (fail==-1){
			  col[i] = pa[i][pass];
			  col[pa[i][pass]] = i;
			  know[i] = 1;
			  know[pa[i][pass]] = 1;
		  }
		  else{
			  for (int j=0;j<3;j++){
				  if (j==like || j==fail) continue;
				  col[i] = pa[i][j];
				  col[pa[i][j]] = i;
				  know[i] = 1;
				  know[pa[i][j]] = 1;
			  }
		  }
	  }
	  ll out[2*N+5];
	  memset(out,0,sizeof(out));
	  for (int i = 1; i <= 2*N; i++) {
		  if (out[i]==1) continue;
		  //cout << i << " " << col[i] << "\n";
		  Answer(i,col[i]);
		  out[i]=1;
		  out[col[i]]=1;
	  }
  }
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:163:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |      if (j!=used.size()) continue;
      |          ~^~~~~~~~~~~~~
chameleon.cpp:175:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |       if (q1!=temp.size()){
      |           ~~^~~~~~~~~~~~~

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