Submission #360131

#	Time	Username	Problem	Language	Result	Execution time	Memory
360131		spatarel	ICC (CEOI16_icc)	C++17	100 / 100	152 ms	620 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10