제출 #1092840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1092840		Fran	ICC (CEOI16_icc)	C++17	100 / 100	85 ms	656 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 101;

int rang[N];

vector<int> ver[N];

int qry(vector<int> a, vector<int> b) {
  return query(a.size(), b.size(), &a[0], &b[0]);
}

int find(vector<int> a, vector<int> b) {
  if(a.size() == 1) {
    return a[0];
  }

  int mid = a.size()/2;
  auto lv = vector(a.begin(), a.begin()+mid), rv = vector(a.begin()+mid, a.end());
  return qry(lv, b) ? find(lv, b) : find(rv, b);
}


void run(int n) {
  iota(rang, rang+n+1, 0);
  for(int i = 1; i <= n; ++i) ver[i].push_back(i);

  for(int e = 0; e < n - 1; ++e) {
    vector<int> root;
    for(int i = 1; i <= n; ++i) if(rang[i] == i) root.push_back(i);

    int roots = root.size();
    int x = 0, k = -1;
    for(int i = 0; (1 << i) < roots; ++i) {
      vector<int> a, b;
      for(int j = 0; j < roots; ++j) {
        auto &v = (j >> i) & 1 ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end());
      }
      if(qry(a, b)) {
        x ^= (1 << i);
        k = i;
      }
    }
    int y = 0;

    for(int i = 0; (1 << i) < roots; ++i) {
      if(i == k) continue;
      vector<int> a, b;
      for(int j = 0; j < roots; ++j) {
        auto &v = j & (1 << i | 1 << k) ? a : b;
        v.insert(v.end(), ver[root[j]].begin(), ver[root[j]].end()); 
      }
      if(!qry(a, b)) y ^= (1 << i);
    }

    x ^= y;

    int u = find(ver[root[x]], ver[root[y]]);
    int v = find(ver[root[y]], ver[root[x]]);

    setRoad(u, v);

    for(auto& x : ver[rang[u]]) {
      rang[x] = rang[v];
      ver[rang[v]].push_back(x);
    }

  }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10