oj.uz

Submission #360129

# Submission time Handle Problem Language Result Execution time Memory
360129 2021-01-27T14:08:25 Z spatarel ICC (CEOI16_icc) C++17
90 / 100
 170 ms 624 KB 
#include "icc.h"
#include <stdio.h>
#include <vector>

const int MAX_N = 100;

int comp[1 + MAX_N];

int query(std::vector<int> a, std::vector<int> b) {
  return query(a.size(), b.size(), a.data(), b.data());
}

void run(int n) {
  for (int i = 1; i <= n; i++) {
    comp[i] = i - 1;
  }
  for (int comps = n; comps > 1; comps--) {
    int log2Comps = 0;
    int copy = comps - 1;
    while (copy > 0) {
      copy /= 2;
      log2Comps++;
    }
    int XOR = 0;
    std::vector<int> A, B;
    for (int bi = 0; bi < log2Comps; bi++) {
      int bit = 1 << bi;
      std::vector<int> a, b;
      for (int i = 1; i <= n; i++) {
        if (comp[i] & bit) {
          a.push_back(i);
        } else {
          b.push_back(i);
        }
      }
      int q = query(a, b);
      XOR ^= q << bi;
      if (q) {
        A = a;
        B = b;
      }
    }
    //for (int i = 1; i <= n; i++) {
    //  printf("%d ", comp[i]);
    //}
    //printf("\n");
    //printf("%d %d - %d %d\n", comps, log2Comps, (int)A.size(), (int)B.size());
    //fflush(stdout);
    for (int _ = 0; _ < 2; _++) { // FIXME
      while (A.size() > 1) {
      std::vector<int> A1, A2;
        for (int i = 0; i < (int)A.size(); i++) {
          if (i % 2) {
            A1.push_back(A[i]);
          } else {
            A2.push_back(A[i]);
          }
        }
        if (query(A1, B)) {
          A = A1;
        } else {
          A = A2;
        }
      }
      std::swap(A, B);
    }
    //printf("mamax\n");
    //fflush(stdout);
    //printf("%d %d\n", (int)A.size(), (int)B.size());
    //fflush(stdout);
    setRoad(A[0], B[0]);
    //printf("tata\n");
    //fflush(stdout);
    int compA = comp[A[0]];
    int compB = comp[B[0]];
    for (int i = 1; i <= n; i++) {
      if (comp[i] == compA) {
        comp[i] = compB;
      }
    }
    for (int i = 1; i <= n; i++) {
      if (comp[i] == comps - 1) {
        comp[i] = compA;
      }
    }
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 492 KB Ok! 127 queries used.
2 Correct 8 ms 492 KB Ok! 123 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 492 KB Ok! 674 queries used.
2 Correct 50 ms 620 KB Ok! 670 queries used.
3 Correct 53 ms 620 KB Ok! 666 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 620 KB Ok! 1678 queries used.
2 Correct 148 ms 492 KB Ok! 1634 queries used.
3 Correct 141 ms 620 KB Ok! 1657 queries used.
4 Correct 142 ms 492 KB Ok! 1647 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 620 KB Ok! 1628 queries used.
2 Correct 144 ms 492 KB Ok! 1632 queries used.
3 Correct 140 ms 580 KB Ok! 1620 queries used.
4 Correct 170 ms 624 KB Ok! 1663 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 492 KB Ok! 1617 queries used.
2 Correct 149 ms 492 KB Ok! 1636 queries used.
3 Correct 145 ms 620 KB Ok! 1644 queries used.
4 Correct 144 ms 624 KB Ok! 1651 queries used.
5 Correct 144 ms 492 KB Ok! 1650 queries used.
6 Correct 144 ms 492 KB Ok! 1676 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 492 KB Too many queries! 1631 out of 1625
2 Halted 0 ms 0 KB -