Submission #1032491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032491		aymanrs	Chameleon's Love (JOI20_chameleon)	C++14	0 / 100	21 ms	500 KiB

chameleon

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

char samecol(int i, vector<int> g[], int j){
  if(i==j) return 1;
  for(int k : g[i]){
    int r = samecol(k, g, j);
    if(r) return -r;
  }
  return 0;
}
void Solve(int N) {
  bool v[2*N+1] = {false};
  int d[2*N+1] = {0};
  vector<int> g[2*N+1];
  auto adde = [&g](int a, int b) -> void {
    g[a].push_back(b);
    g[b].push_back(a);
  };
  for(int i = 1;i <= N;i++){
    vector<int> s;
    for(int j = N+1;j <= 2*N;j++){
      if(d[j]<3) s.push_back(j);
    }
    int l = 0, r = s.size()-1, m, te;
    s.push_back(i);
    if(s.size()==2) goto afbs;
    while(l<r){
      m = l+r>>1;
      te = Query(vector<int>(s.begin()+l, s.begin()+m+1));
      swap(s.back(), s[m+1]);
      if(Query(vector<int>(s.begin()+l, s.begin()+m+2)) <= te){
        r = m;
      } else l=m+1;
      swap(s.back(), s[m+1]);
    }
    afbs:
    adde(s[l], i);
    d[s[l]]++;d[i]++;
    while(d[i]<3){
      s.clear();
      for(int j = N+1;j <= 2*N;j++){
        if(d[j]<3 && none_of(g[i].begin(), g[i].end(), [&j](int k){return k==j;})) s.push_back(j);
      }
      if(s.empty()) break;
      l = 0; r = s.size()-1;
      te = Query(s);
      s.push_back(i);
      if(Query(s) > te) {
        break;
      }
      if(s.size()==2) goto affbs;
      while(l<r){
        m = l+r>>1;
        te = Query(vector<int>(s.begin()+l, s.begin()+m+1));
        swap(s.back(), s[m+1]);
        if(Query(vector<int>(s.begin()+l, s.begin()+m+2)) <= te){
          r = m;
        } else l=m+1;
        swap(s.back(), s[m+1]);
      }
      affbs:
      adde(s[l], i);
      d[s[l]]++;d[i]++;
    }
  }
  while(true){
    bool ok = false;
    for(int i = 1;i <= 2*N;i++){
      if(d[i]==1){
        d[i]=d[g[i][0]]=-1;
        ok = true;
        Answer(i, g[i][0]);
      }
    }
    if(!ok) break;
  }
  int L[2*N+1];
  fill(L, L+2*N+1, -1);
  for(int i = 1;i <= 2*N;i++){
    if(d[i]==-1) continue;
    for(int j = 0;j < 3;j++){
      if(L[g[i][j]] == i || d[g[i][j]]==-1) continue;
      if(Query({i, g[i][(j+2)%3], g[i][(j+1)%3]})==1){
        L[i] = g[i][j];
        break;
      }
    }
  }
  for(int i = 1;i <= N;i++){
    if(d[i]==-1) continue;
    for(int j = 0;j < 3;j++){
      if(L[g[i][j]] != -1 && L[g[i][j]] != i && L[i] != g[i][j]){
        Answer(i, g[i][j]);
        break;
      }
    }
  }
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |       m = l+r>>1;
      |           ~^~
chameleon.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         m = l+r>>1;
      |             ~^~
chameleon.cpp:14:8: warning: unused variable 'v' [-Wunused-variable]
   14 |   bool v[2*N+1] = {false};
      |        ^

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