Submission #1306876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306876		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	50 / 100	239 ms	1672 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

#define trace(x) for (auto &el : x) cerr << el << " "

using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;

vi find_complete(int n, vi X, vi Y) {
  vi G(n, 0);

  auto first_k_colours = [&](int target, int k) {
    if (k >= n) {
      vi e(n, n-1); e[target] = 1;
      return e;
    }

    vi e(n, n); e[target] = -1;

    int colour = 0;
    for (int i = 0; i < target && k > 0; i++) {
      e[i] = colour;
      k--; colour++;
    }

    for (int i = target + 1; i < n && k > 0; i++) {
      e[i] = colour;
      k--; colour++;
    }

    return e;
  };

  auto expected_cmps = [](vi experiment) {
    int sc = 0; for (auto el : experiment) if (el == -1) sc++;
    int sz = set<int>(experiment.begin(), experiment.end()).size();
    if (sc > 0) sz = sz - 1 + sc;

    return sz;
  };
 
  for (int i = 0; i < n; i++) {
    int lo = 0, hi = n;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      vi e = first_k_colours(i, mid);
      int x = perform_experiment(e);

      if (x == expected_cmps(e)) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }

    G[i] = lo - 1;
  }
  return G;
}

/*
  for the case of the graph being a path:
  divide the graph into two disjoint sets ie. XYXYXY

  for each colour, determine for each set X and Y how many elements in the entire graph have colour c
  do this by setting all nodes of the other set to colour c then computing #(expected cmps) - #(actual cmps)

  takes 2n = 500 queries

  now for each colour that appears t > 0 times in a set, launch t binary searches of the form (first node where c appears >= i times?)
  for i in range [1, t]

  the sum of #(appearances in set) over all colours with t>0 is = size of set = n/2
  in total doing this process for both sets will take 2 * (n/2) binary searches that use log₂(n/2) queries each, or for n = 250
  it uses 2 * 125 * 7 = 1750 queries

  in total 1750 + 500 = 2250
*/

vi find_path(int n, vi X, vi Y) {
  vi G(n, 0);

  auto expected_cmps = [&](vi e) {
    int sz = 1; for (int i = 1; i < n; i++) if (!(e[i] == e[i-1] && e[i] != -1)) sz++;
    return sz;
  };

  auto f = [&](int k, int colour, bool set1) {
    vi e(n, n);

    int LC = set1 ? -1 : colour, RC = set1 ? colour : -1;
    for (int i = 0; i < k && (2*i) < n; i++) {
      e[2*i] = LC;
      if (2*i+1 < n) e[2*i+1] = RC;
    }

    return e;
  };

  auto g = [&](vi base, int colour, vi indices) {
    for (auto el : indices) if (base[el] != n) base[el] = colour;
    return base;
  };

  // set 1 is U.U.U.U., set2 is .V.V.V.V
  int s1 = n/2, s2 = (n)/2;
  for (int c = 0; c < n; c++) {
    vi e1 = f(s1, c, true), e2 = f(s2, c, false);
    int x1 = perform_experiment(e1), x2 = perform_experiment(e2);
    if (x1 != expected_cmps(e1)) {
      vi found; 
      while (expected_cmps(g(f(s1, c, true), c, found)) != x1) {
        int lo = 0, hi = s1;
        while (lo < hi) {
          int mid = lo + (hi - lo) / 2;
          vi e = g(f(mid, c, true), c, found);

          if (perform_experiment(e) == expected_cmps(e)) {
            lo = mid + 1;
          } else {
            hi = mid;
          }
        }

        found.push_back(2*(lo-1));
        G[2*(lo-1)] = c;
      }
    }
    if (x2 != expected_cmps(e2)) {
      vi found; 
      while (expected_cmps(g(f(s2, c, false), c, found)) != x2) {
        int lo = 0, hi = s2;
        while (lo < hi) {
          int mid = lo + (hi - lo) / 2;
          vi e = g(f(mid, c, false), c, found);

          if (perform_experiment(e) == expected_cmps(e)) {
            lo = mid + 1;
          } else {
            hi = mid;
          }
        }

        found.push_back(2*lo-1);
        G[2*lo-1] = c;
      }
    }

    if (n % 2 == 1) {
      vi e(n, n);
      e[n-2] = c; e[n-1] = -1;

      if (perform_experiment(e) == 2) {
        G[n-1] = c;
      }
    }
  }

  return G;
}

vi find_small(int n, vi X, vi Y) {
  vi G(n, 0);
  for (int i = 0; i < n; i++) {
    for (int c = 0; c < n; c++) {
      vi e(n, c); e[i] = -1;
      if (perform_experiment(e) == 1) G[i] = c;
    }
  }

  return G;
}

struct DSU {
  int n, cmps; vi par;
  DSU() {};
  DSU(int N) {
    n = cmps = N; for (int i = 0; i < n; i++) par.push_back(i);
  }

  int find(int v) {
    if(par[v] == v) return v;
    return par[v] = find(par[v]);
  }

  void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) {
      par[b] = a;
      cmps--;
    }
  }
};

int count_expected(int n, vi X, vi Y, vi e) {
  auto dsu = DSU(n);
  for (int i = 0; i < X.size(); i++) {
    if (e[X[i]] != e[Y[i]] || e[X[i]] == -1 || e[Y[i]] == -1) continue;
    dsu.unite(X[i], Y[i]);
  }

  return dsu.cmps;
}

vi find_general(int n, vi X, vi Y) {
  vector<vi> adj(n, vi()); for (int i = 0; i < X.size(); i++) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }

  vi G(n, 0), order;
  queue<int> q({0}); G[0] = 1;

  while (!q.empty()) {
    int u = q.front(); q.pop();
    order.push_back(u);

    for (auto v : adj[u]) {
      if (G[v]) continue;
      q.push(v); G[v]++;
    }
  }

  G.assign(n, -1);
  vector<vi> cmps;
  for (auto u : order) {
    bool found = true;

    vi all_groups;
    while (found) {
      found = false;

      vector<int> alive;
      for (int i = 0; i < cmps.size(); i++)
        if (cmps[i].back() != u) alive.push_back(i);

      int lo = 0, hi = alive.size();

      while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        vi e(n, n); e[u] = -1; for (int i = 0; i <= mid; i++) for (auto el : cmps[alive[i]]) e[el] = i;
        int x = count_expected(n, X, Y, e); for (int i = 0; i <= mid; i++) for (auto el : cmps[alive[i]]) e[el] = -1;

        if (x == perform_experiment(e)) {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      }

      if (lo >= alive.size()) {
        cmps.push_back(vi({u}));
      } else {
        cmps[alive[lo]].push_back(u);
        found = true;
        all_groups.push_back(alive[lo]);
      }
    }

    vi ncmp; for (auto el : all_groups) for (auto vel : cmps[el]) if (vel != u) ncmp.push_back(vel);
    ncmp.push_back(u);

    bool changed = true;
    while (changed) {
      changed = false;

      int pos = -1;
      for (int i = 0; i < cmps.size(); i++) {
        if (cmps[i].back() == u) {
          pos = i;
          break;
        }
      }

      if (pos != -1) {
        changed = true;
        swap(cmps[pos], cmps[cmps.size() - 1]);
        cmps.pop_back();
      }
    }

    cmps.push_back(ncmp);
  }

  // trace(order); cerr << "\n";
  for (int i = 0; i < cmps.size(); i++) for (auto el : cmps[i]) G[el] = i;
  return G;
}

vi find_colours(int n, vi X, vi Y) {
  // if (X.size() == (n * (n-1) / 2)) {
  //   return find_complete(n, X, Y);
  // } else if (n <= 50) {
  //   return find_small(n, X, Y);
  // } else if (X.size() == n-1) {
  //   return find_path(n, X, Y);
  // }

  vi G = find_general(n, X, Y);
  return G;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 18 / 36