Submission #1057235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057235		huutuan	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	20 ms	552 KiB

chameleon

#include "chameleon.h"

#include <bits/stdc++.h>

using namespace std;

namespace solver{
   int fake_query(vector<int> v){
      for (int &i:v) ++i;
      return Query(v);
   }
   void fake_answer(int a, int b){
      if (a<b) Answer(a+1, b+1);
   }
   void solve(int n){
      vector<vector<int>> g(n*2);
      vector<int> v(n*2);
      iota(v.begin(), v.end(), 0);
      for (int _=0; _<3; ++_){
         vector<int> v1, v2;
         for (auto &i:v){
            v1.push_back(i);
            if (fake_query(v1)!=(int)v1.size()){
               v1.pop_back();
               v2.push_back(i);
            }
         }
         auto query=[&](int i, int l, int r){
            vector<int> tmp(v1.begin()+l, v1.begin()+r+1);
            tmp.push_back(i);
            return fake_query(tmp)!=tmp.size();
         };
         v.clear();
         for (int i:v2){
            int st=0;
            while ((int)g[i].size()<3){
               if (st && !query(i, st, (int)v1.size()-1)) break;
               int l=st, r=(int)v1.size()-2;
               while (l<=r){
                  int mid=(l+r)>>1;
                  if (query(i, st, mid)) r=mid-1;
                  else l=mid+1;
               }
               g[i].push_back(v1[l]);
               g[v1[l]].push_back(i);
               st=l+1;
            }
            if ((int)g[i].size()<3) v.push_back(i);
         }
      }
      for (int i=0; i<n*2; ++i){
         if ((int)g[i].size()==1) fake_answer(i, g[i][0]);
      }
      vector<int> L(n*2, -1);
      for (int i=0; i<n*2; ++i){
         if ((int)g[i].size()==3){
            if (fake_query({i, g[i][0], g[i][1]})==1) L[i]=g[i][2];
            else if (fake_query({i, g[i][1], g[i][2]})==1) L[i]=g[i][0];
            else L[i]=g[i][1];
         }
      }
      for (int i=0; i<n*2; ++i) if ((int)g[i].size()==3){
         int t=g[i][0];
         if (L[i]==g[i][0] || L[g[i][0]]==i){
            if (L[i]==g[i][1] || L[g[i][1]]==i) fake_answer(i, g[i][2]);
            else fake_answer(i, g[i][1]);
         }else fake_answer(i, g[i][0]);
      }
   }
}

void Solve(int N) {
   solver::solve(N);
}

Compilation message (stderr)

chameleon.cpp: In lambda function:
chameleon.cpp:31:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             return fake_query(tmp)!=tmp.size();
      |                    ~~~~~~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void solver::solve(int)':
chameleon.cpp:63:14: warning: unused variable 't' [-Wunused-variable]
   63 |          int t=g[i][0];
      |              ^

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