Submission #38836

#	Time	Username	Problem	Language	Result	Execution time	Memory
38836		cheater2k	ICC (CEOI16_icc)	C++14	100 / 100	169 ms	2224 KiB

icc

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

// int query(int size_a, int size_b, int a[], int b[]);
// void setRoad(int a, int b);

const int MAX = 105;

int n, ncomp;
vector<int> G[MAX];
vector<int> comp[MAX];
vector<int> buf[2];
bool vis[MAX];

int tmp[2][MAX];
int Query(vector<int> &a, vector<int> &b) {
  for (int i = 0; i < a.size(); ++i) tmp[0][i] = a[i] + 1;
  for (int i = 0; i < b.size(); ++i) tmp[1][i] = b[i] + 1;
  return query(a.size(), b.size(), tmp[0], tmp[1]);
}

void reset() {
  ncomp = 0;
  for (int i = 0; i < n; ++i) comp[i].clear(), vis[i] = 0;

  for (int i = 0; i < n; ++i) if (!vis[i]) {
    queue <int> q; q.push(i); vis[i] = 1;
    while(!q.empty()) {
      int u = q.front(); q.pop();
      comp[ncomp].push_back(u);
      for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i]; 
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
    ++ncomp;
  }
}

vector<int> modify(vector<int> &a) {
  vector<int> ret;
  for (int i = 0; i < a.size(); ++i) {
    int cur = a[i];
    for (int j = 0; j < comp[cur].size(); ++j) ret.push_back(comp[cur][j]);
  }
  return ret;
}

int ask(vector<int> &a, vector<int> &b, int l, int r) {
  if (l == r) return a[l];
  
  int mid = ((l + r) >> 1);

  vector<int> lef;
  for (int i = l; i <= mid; ++i) lef.push_back(a[i]);
  if (Query(lef, b)) return ask(a, b, l, mid); // left
  else return ask(a, b, mid + 1, r); // right
}

void solve() {
  reset();
  // the current number of nodes: ncomp [0...ncomp-1]
  int nbit = (int)log2(ncomp - 1) + 1;
  for (int bit = 0; bit < nbit; ++bit) {
    buf[0].clear();
    buf[1].clear();
    for (int i = 0; i < ncomp; ++i) {
      buf[i >> bit & 1].push_back(i);
    }   
    buf[0] = modify(buf[0]);
    buf[1] = modify(buf[1]);

    int ans = Query(buf[0], buf[1]);
    if (ans) { // different at {bit}
      break;
    }
  }

  int u = ask(buf[0], buf[1], 0, buf[0].size() - 1);
  int v = ask(buf[1], buf[0], 0, buf[1].size() - 1);

  setRoad(u + 1, v + 1);
  G[u].push_back(v); G[v].push_back(u);
}

void run(int N) {
  n = N;
  for (int i = 1; i < n; ++i) solve();
}

Compilation message (stderr)

icc.cpp: In function 'int Query(std::vector<int>&, std::vector<int>&)':
icc.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); ++i) tmp[0][i] = a[i] + 1;
                     ^
icc.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.size(); ++i) tmp[1][i] = b[i] + 1;
                     ^
icc.cpp: In function 'void reset()':
icc.cpp:32:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < G[u].size(); ++i) {
                         ^
icc.cpp: In function 'std::vector<int> modify(std::vector<int>&)':
icc.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); ++i) {
                     ^
icc.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < comp[cur].size(); ++j) ret.push_back(comp[cur][j]);
                       ^

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