oj.uz

Submission #38836

# Submission time Handle Problem Language Result Execution time Memory
38836 2018-01-07T05:21:28 Z cheater2k ICC (CEOI16_icc) C++14
100 / 100
 169 ms 2224 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2084 KB Ok! 95 queries used.
2 Correct 3 ms 2088 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2088 KB Ok! 530 queries used.
2 Correct 46 ms 2088 KB Ok! 647 queries used.
3 Correct 53 ms 2088 KB Ok! 647 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 2216 KB Ok! 1350 queries used.
2 Correct 169 ms 2220 KB Ok! 1595 queries used.
3 Correct 153 ms 2216 KB Ok! 1594 queries used.
4 Correct 133 ms 2220 KB Ok! 1496 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2216 KB Ok! 1462 queries used.
2 Correct 119 ms 2216 KB Ok! 1411 queries used.
3 Correct 129 ms 2224 KB Ok! 1551 queries used.
4 Correct 123 ms 2216 KB Ok! 1390 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2220 KB Ok! 1546 queries used.
2 Correct 143 ms 2220 KB Ok! 1580 queries used.
3 Correct 146 ms 2224 KB Ok! 1622 queries used.
4 Correct 133 ms 2224 KB Ok! 1539 queries used.
5 Correct 119 ms 2216 KB Ok! 1420 queries used.
6 Correct 156 ms 2220 KB Ok! 1517 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2216 KB Ok! 1591 queries used.
2 Correct 143 ms 2216 KB Ok! 1604 queries used.