oj.uz

Submission #360131

# Submission time Handle Problem Language Result Execution time Memory
360131 2021-01-27T14:09:34 Z spatarel ICC (CEOI16_icc) C++17
100 / 100
 152 ms 620 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;
        break;
      }
    }
    //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; _++) {
      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 7 ms 492 KB Ok! 100 queries used.
2 Correct 6 ms 492 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Ok! 547 queries used.
2 Correct 46 ms 568 KB Ok! 673 queries used.
3 Correct 45 ms 512 KB Ok! 660 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 492 KB Ok! 1458 queries used.
2 Correct 146 ms 492 KB Ok! 1634 queries used.
3 Correct 149 ms 572 KB Ok! 1624 queries used.
4 Correct 134 ms 492 KB Ok! 1541 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 620 KB Ok! 1532 queries used.
2 Correct 133 ms 492 KB Ok! 1546 queries used.
3 Correct 140 ms 576 KB Ok! 1615 queries used.
4 Correct 145 ms 492 KB Ok! 1580 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 620 KB Ok! 1620 queries used.
2 Correct 142 ms 492 KB Ok! 1627 queries used.
3 Correct 143 ms 620 KB Ok! 1632 queries used.
4 Correct 141 ms 620 KB Ok! 1635 queries used.
5 Correct 133 ms 620 KB Ok! 1568 queries used.
6 Correct 135 ms 492 KB Ok! 1571 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 492 KB Ok! 1625 queries used.
2 Correct 152 ms 492 KB Ok! 1621 queries used.