제출 #1146064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146064		byunjaewoo	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	44 ms	524 KiB

chameleon

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

const int N=1010;
int chk[N];
vector<int> adj[N];

void Solve(int N) {
  for(int i=1; i<=2*N; i++) {
    fill(chk+1, chk+2*N+1, -1);
    vector<int> a[2];
    function<void(int, int)> dfs=[&](int curr, int c) {
      chk[curr]=c;
      a[c].push_back(curr);
      for(int next:adj[curr]) if(chk[next]<0) dfs(next, 1-c);
    };
    auto query2=[&](int a, int b) {
      vector<int> tmp;
      tmp.push_back(a), tmp.push_back(b);
      if(Query(tmp)!=1) return false;
      tmp.clear();
      for(int i=1; i<=2*N; i++) if(i!=a && i!=b) tmp.push_back(i);
      return Query(tmp)<=N-1;
    };
    for(int j=1; j<i; j++) if(chk[j]<0) dfs(j, 0);
    for(int j=0; j<2; j++) if(a[j].size()) {
      while(true) {
        a[j].push_back(i);
        if(Query(a[j])==a[j].size()) {
          a[j].pop_back();
          break;
        }
        a[j].pop_back();
        int p=0;
        for(int s=0, e=a[j].size()-1; s<e; ) {
          int m=(s+e)/2;
          vector<int> v;
          for(int k=s; k<=m; k++) v.push_back(a[j][k]);
          v.push_back(i);
          if(Query(v)==v.size()) s=p=m+1;
          else e=m;
        }
        if(query2(i, a[j][p])) Answer(i, a[j][p]);
        adj[i].push_back(a[j][p]), adj[a[j][p]].push_back(i);
        swap(a[j][p], a[j].back()), a[j].pop_back();
      }
    }
  }
}

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