Submission #1306834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306834		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	57 / 100	40 ms	1156 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;
}

struct DSU {
  int n, cmps; vi par;
  DSU() {};
  DSU(int N) {
    n = N; par.resize(n); iota(par.begin(), par.end(), 0);
  }

  DSU(int N, vi X, vi Y, vi E) {
    n = cmps = N; par.resize(n); iota(par.begin(), par.end(), 0);
    for (int i = 0; i < X.size(); i++) {
      if (E[X[i]] == -1 || E[Y[i]] == -1 || E[X[i]] != E[Y[i]]) continue;
      unite(X[i], Y[i]);
    }
  }

  int find(int v) {
    if (v == par[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--;
    }
  }
};

vi find_small(int n, vi X, vi Y) {
  vi G(n, -1);

  for (int i = 0; i < X.size(); i++) {
    int u = X[i], v = Y[i];
    if (G[u] == -1) {
      for (int c = 0; c < n; c++) {
        vi e(n, n); e[u] = -1; e[v] = c;
        auto dsu = DSU(n, X, Y, e);
        int x = dsu.cmps;
        if (x != perform_experiment(e)) {
          G[u] = c;
          break;
        }
      }
    }

    if (G[v] == -1) {
      for (int c = 0; c < n; c++) {
        vi e(n, n); e[v] = -1; e[u] = c;
        auto dsu = DSU(n, X, Y, e);
        int x = dsu.cmps;
        if (x != perform_experiment(e)) {
          G[v] = c;
          break;
        }
      }
    }
  }

  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 (X.size() == n-1) {
    return find_path(n, X, Y);
  } else if (n <= 50) {
    return find_small(n, X, Y);
  }

  vi G(n, 0);
  return G;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 0 / 36