Submission #1289911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289911		lucaskojima	ICC (CEOI16_icc)	C++17	0 / 100	3 ms	616 KiB

icc

#include "bits/stdc++.h"
#include "icc.h"
#define sz(x) (int)size(x)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N   = 100;

int a[N], b[N], cur[N];

void clear() {
  for (int i = 0; i < N; i++) {
    a[i] = 0, b[i] = 0;
  }
}
void clear_cur() {
  for (int i = 0; i < N; i++)
    cur[i] = 0;
}

void run(int n) {
  vector<vector<int>> cmp(n);
  for (int i = 0; i < n; i++)
    cmp[i].push_back(i + 1);

  for (int _ = 0; _ < n - 1; _++) {
    int k = sz(cmp);
    vector<pii> intervals = {{0, k - 1}};
    vector<pii> nxt;

    while (1) {
      for (auto [l, r] : intervals) {
        if (l == r) {
          nxt.push_back({l, r});
          continue;
        }
        int m = (l + r) / 2;
        nxt.push_back({l, m});
        nxt.push_back({m + 1, r});
      }
      swap(intervals, nxt);

      clear();
      int size_a = 0;
      for (int i = 0; i < sz(intervals); i += 2) {
        auto [l, r] = intervals[i];
        for (int j = l; j <= r; j++)
          for (int x : cmp[j])
            a[size_a++] = x;
      }
      int size_b = 0;
      for (int i = 1; i < sz(intervals); i += 2) {
        auto [l, r] = intervals[i];
        for (int j = l; j <= r; j++)
          for (int x : cmp[j])
            b[size_b++] = x;
      }

      if (query(size_a, size_b, a, b) == 1) {

        auto recA = [&](auto recA, int l, int r) -> int {
          if (l == r) return a[l];
          int m = (l + r) / 2;

          clear_cur();
          int size = 0;
          for (int i = l; i <= m; i++)
            cur[size++] = a[i];

          if (query(size, size_b, cur, b) == 1)
            return recA(recA, l, m);
          else
            return recA(recA, m + 1, r);
        };
        auto recB = [&](auto recB, int l, int r) -> int {
          if (l == r) return b[l];
          int m = (l + r) / 2;

          clear_cur();
          int size = 0;
          for (int i = l; i <= m; i++)
            cur[size++] = b[i];

          if (query(size, size_a, cur, a) == 1)
            return recB(recB, l, m);
          else
            return recB(recB, m + 1, r);
        };

        int A = recA(recA, 0, size_a - 1);
        int B = recB(recB, 0, size_b - 1);
        setRoad(A, B);

        vector<vector<int>> nxt_cmp;
        int id = -1;
        for (int i = 0; i < k; i++) {
          bool f = false;
          for (int x : cmp[i])
            if (x == A || x == B)
              f = true;

          if (!f) {
            nxt_cmp.push_back(cmp[i]);
          } else {
            if (id == -1) {
              id = i;
              nxt_cmp.push_back(cmp[i]);
            } else {
              for (int x : cmp[i])
                nxt_cmp[id].push_back(x);
            }
          }
        }
        swap(cmp, nxt_cmp);
        break;
      }
    }
  }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10