oj.uz

답안 #94774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94774 2019-01-23T15:40:56 Z tincamatei CEOI16_icc (CEOI16_icc) C++14
61 / 100
 206 ms 632 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);
}

int expected;

bool randomSplit(int n, vector<int> &sa, vector<int> &sb) {
  for(int i = 1; i <= n; ++i)
    rperm[i] = rand() % 2;
  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];

  expected++;
  //assert(expected < 400); // Expected Value screwed me over

  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:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sa.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp:100: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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 504 KB Ok! 104 queries used.
2 Correct 8 ms 504 KB Ok! 116 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 504 KB Ok! 550 queries used.
2 Correct 55 ms 504 KB Ok! 839 queries used.
3 Correct 57 ms 552 KB Ok! 837 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 504 KB Ok! 1520 queries used.
2 Correct 206 ms 560 KB Ok! 2154 queries used.
3 Correct 158 ms 604 KB Ok! 1709 queries used.
4 Correct 167 ms 604 KB Ok! 1754 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 504 KB Ok! 1713 queries used.
2 Correct 160 ms 504 KB Ok! 1725 queries used.
3 Correct 177 ms 504 KB Ok! 1874 queries used.
4 Correct 155 ms 604 KB Ok! 1617 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 187 ms 504 KB Too many queries! 1926 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 632 KB Too many queries! 1942 out of 1625
2 Halted 0 ms 0 KB -