제출 #257756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
257756		Bruteforceman	카멜레온의 사랑 (JOI20_chameleon)	C++14	100 / 100	77 ms	760 KiB

chameleon

#include "bits/stdc++.h"
#include "chameleon.h"
using namespace std;
namespace {
  const int maxn = 5e3 + 10;
  vector <int> g[maxn];
  int col[maxn];

  void addEdge(int i, int j) {
    g[i].push_back(j);
    g[j].push_back(i);
  }
  void dfs(int x) {
    for(int i : g[x]) {
      if(col[i] == -1) {
        col[i] = col[x] ^ 1;
        dfs(i);
      }
    }
  }
  void partition(int V, vector <int> &u, vector <int> &v) {
    for(int i = 1; i <= V; i++) {
      col[i] = -1;
    }
    for(int i = 1; i <= V; i++) {
      if(col[i] == -1) {
        col[i] = 0;
        dfs(i);
      }
    }
    for(int i = 1; i <= V; i++) {
      if(col[i] == 0) u.push_back(i);
      else v.push_back(i);
    }
  }
  bool makeEdge(vector <int> &v, int i) {
    if(v.size() == 0) return false;
    vector <int> u = v;
    u.push_back(i);
    if(Query(u) == u.size()) return false;
    int l = 0, r = v.size() - 1;
    while(l < r) {
      int mid = (l + r) >> 1;
      vector <int> aux = v;
      aux.resize(mid + 1);
      aux.push_back(i);
      if(Query(aux) == aux.size()) l = mid + 1;
      else r = mid;
    }
    addEdge(v[l], i);
    v.erase(v.begin() + l);
    return true;
  }
  bool makeEdges(vector <int> &v, int i) {
    while(makeEdge(v, i));
  }
}  // namespace

void Solve(int N) {
  for(int i = 1; i <= 2 * N; i++) {
    vector <int> u, v;
    partition(i - 1, u, v);
    makeEdges(u, i);
    makeEdges(v, i);
  }
  set <pair <int, int>> s;
  set <int> done;
  for(int i = 1; i <= 2 * N; i++) {
    if(g[i].size() == 1) {
      int p = i, q = g[i].front();
      if(p > q) swap(p, q);
      s.insert(make_pair(p, q));
      done.insert(p);
      done.insert(q);
    }
  }
  map <pair <int, int>, int> cnt;
  for(int i = 1; i <= 2 * N; i++) {
    if(done.count(i) == 0) {
      for(int x = 0; x < 3; x++) {
        for(int y = x + 1; y < 3; y++) {
          int p = g[i][x], q = g[i][y];
          if(Query(vector <int> ({p, q, i})) == 1) {
            int j = p, k = i;
            if(j > k) swap(j, k);
            cnt[make_pair(j, k)] += 1;
            j = q; k = i;
            if(j > k) swap(j, k);
            cnt[make_pair(j, k)] += 1;
          }
        }
      }
    }
  }
  for(auto i : cnt) if(i.second == 2) s.insert(i.first);
  for(auto i : s) {
    Answer(i.first, i.second);
  }
}

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

chameleon.cpp: In function 'bool {anonymous}::makeEdge(std::vector<int>&, int)':
chameleon.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(u) == u.size()) return false;
        ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(Query(aux) == aux.size()) l = mid + 1;
          ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'bool {anonymous}::makeEdges(std::vector<int>&, int)':
chameleon.cpp:56:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^

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