oj.uz

Submission #94766

# Submission time Handle Problem Language Result Execution time Memory
94766 2019-01-23T15:19:32 Z tincamatei ICC (CEOI16_icc) C++14
61 / 100
 193 ms 596 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 106 queries used.
2 Correct 7 ms 504 KB Ok! 106 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 504 KB Ok! 534 queries used.
2 Correct 57 ms 568 KB Ok! 844 queries used.
3 Correct 53 ms 560 KB Ok! 824 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 596 KB Ok! 1565 queries used.
2 Correct 193 ms 560 KB Ok! 2164 queries used.
3 Correct 151 ms 504 KB Ok! 1695 queries used.
4 Correct 155 ms 592 KB Ok! 1752 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 504 KB Ok! 1723 queries used.
2 Correct 142 ms 560 KB Ok! 1715 queries used.
3 Correct 159 ms 504 KB Ok! 1882 queries used.
4 Correct 143 ms 592 KB Ok! 1621 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 560 KB Too many queries! 1922 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 504 KB Too many queries! 1908 out of 1625
2 Halted 0 ms 0 KB -