제출 #932960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932960		AdamGS	카멜레온의 사랑 (JOI20_chameleon)	C++17	100 / 100	47 ms	788 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1007;
vector<int>V[LIM];
map<pair<int,int>,int>mp;
int kol[LIM];
void DFS(int x, int k) {
  kol[x]=k;
  for(auto i : V[x]) if(!kol[i]) DFS(i, k^3);
}
int szukaj(vector<int>A, int x) {
  vector<int>X;
  for(auto i : A) X.pb(i+1);
  X.pb(x+1);
  int p=Query(X);
  if(p==X.size()) return -1;
  int po=0, ko=A.size()-1;
  while(po<ko) {
    int sr=(po+ko)/2;
    X.clear();
    rep(i, sr+1) X.pb(A[i]+1);
    X.pb(x+1);
    p=Query(X);
    if(p==X.size()) po=sr+1; else ko=sr;
  }
  return A[po];
}
void dodaj(int a, int b) {
  if(a>b) swap(a, b);
  ++mp[{a, b}];
  if(mp[{a, b}]==2) {
    Answer(a+1, b+1);
  }
}
void Solve(int n) {
  rep(i, 2*n) {
    rep(j, i) kol[j]=0;
    rep(j, i) if(!kol[j]) DFS(j, 1);
    vector<int>A, B;
    rep(j, i) if(kol[j]==1) A.pb(j); else B.pb(j);
    rep(xd, 2) {
      while(true) {
        int p=szukaj(A, i);
        if(p==-1) break;
        vector<int>tmp;
        for(auto i : A) if(i!=p) tmp.pb(i);
        A=tmp;
        V[p].pb(i);
        V[i].pb(p);
      }
      A=B;
    }
  }
  rep(i, 2*n) {
    if(V[i].size()==1) {
      dodaj(i, V[i][0]);
      continue;
    }
    vector<int>X;
    X.pb(i+1);
    X.pb(V[i][0]+1);
    X.pb(V[i][1]+1);
    if(Query(X)==1) {
      dodaj(i, V[i][0]);
      dodaj(i, V[i][1]);
      continue;
    }
    X[1]=V[i][2]+1;
    if(Query(X)==1) {
      dodaj(i, V[i][1]);
      dodaj(i, V[i][2]);
      continue;
    }
    dodaj(i, V[i][0]);
    dodaj(i, V[i][2]);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'int szukaj(std::vector<int>, int)':
chameleon.cpp:22:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if(p==X.size()) return -1;
      |      ~^~~~~~~~~~
chameleon.cpp:30:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if(p==X.size()) po=sr+1; else ko=sr;
      |        ~^~~~~~~~~~

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