Submission #94766

#	Time	Username	Problem	Language	Result	Execution time	Memory
94766		tincamatei	ICC (CEOI16_icc)	C++14	61 / 100	193 ms	596 KiB

icc

#include <bits/stdc++.h>

using namespace std;

#ifdef HOME

int query(int size_a, int size_b, int a[], int b[]) {
  printf("{");
  for(int i = 0; i < size_a; ++i)
    printf("%d, ", a[i]);
  printf("};{");
  for(int i = 0; i < size_b; ++i)
    printf("%d, ", b[i]);
  printf("}");
  int x;
  scanf("%d", &x);
  return x;
}

void setRoad(int a, int b) {
  printf("Constructed: %d %d\n", a, b);
}

#else

#include "icc.h"

int query(int, int, int *, int *);
void setRoad(int a, int b);

#endif

const int MAX_N = 100;

int a[MAX_N], b[MAX_N], topa, topb;
int sef[1+MAX_N];
int rperm[1+MAX_N];

int myfind(int x) {
  if(x == sef[x]) return x;

  sef[x] = myfind(sef[x]);
  return sef[x];
}

void myunion(int a, int b) {
  int sa = myfind(a), sb = myfind(b);
  sef[sa] = sb;
}

int binsrc(const vector<int> &sa, const vector<int> &sb) {
  int st = -1, dr = (int)sa.size() - 1;

  topa = 0;
  for(int i = 0; i < sb.size(); ++i)
    a[topa++] = sb[i];

  while(dr - st > 1) {
    int mid = (st + dr) / 2;

    topb = 0;
    for(int i = 0; i <= mid; ++i)
      b[topb++] = sa[i];

    if(query(topa, topb, a, b))
      dr = mid;
    else
      st = mid;
  }

  return sa[dr];
}

void solveSplit(const vector<int> sa, const vector<int> sb) {
  int n1, n2;
  n1 = binsrc(sa,   sb);
  n2 = binsrc(sb, {n1});

  setRoad(n1, n2);
  myunion(n1, n2);
}

bool randomSplit(int n, vector<int> &sa, vector<int> &sb) {
  random_shuffle(rperm, rperm + 1 + n);
  sa.clear();
  sb.clear();
  for(int i = 1; i <= n; ++i) {
    if(rperm[myfind(i)] % 2 == 0)
      sa.push_back(i);
    else
      sb.push_back(i);
  }

  topa = topb = 0;
  for(int i = 0; i < sa.size(); ++i)
    a[topa++] = sa[i];
  for(int i = 0; i < sb.size(); ++i)
    b[topb++] = sb[i];

  if(query(topa, topb, a, b))
    return true;
  return false;
}

void split(int n, vector<int> &sa, vector<int> &sb) {
  while(!randomSplit(n, sa, sb));
}

void run(int n) {
  srand(time(NULL));

  for(int i = 1; i <= n; ++i)
    sef[i] = rperm[i] = i;

  for(int i = 0; i < n - 1; ++i) {
    vector<int> sa, sb;
    split(n, sa, sb);
    solveSplit(sa, sb);
  }
}

#ifdef HOME

int main() {
  int n;

  scanf("%d", &n);

  run(n);
  return 0;
}

#endif

Compilation message (stderr)

icc.cpp: In function 'int binsrc(const std::vector<int>&, const std::vector<int>&)':
icc.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sb.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp: In function 'bool randomSplit(int, std::vector<int>&, std::vector<int>&)':
icc.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sa.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sb.size(); ++i)
                  ~~^~~~~~~~~~~

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