Submission #1246661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246661		CyberCow	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	106 ms	1160 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v[300];

int p[300], sz[300];

int qan = 0;

void make_set(int i)
{
  p[i] = i;
  sz[i] = 1;
  qan++;
}

int get_papa(int i)
{
  if(p[i] == i)return i;
  return p[i] = get_papa(p[i]);
}

void union_set(int a, int b)
{
  a = get_papa(a);
  b = get_papa(b);
  if(a == b)return;
  if(sz[a] > sz[b])swap(a, b);
  p[a] = b;
  sz[b] += sz[a];
  qan--;
}

int NN;

vector<int> XX, YY;

int perform_experimentQ(vector<int> &a)
{
  int x = perform_experiment(a); 
  qan = 0;
  for (int i = 0; i < a.size(); i++)
  {
    if(a[i] == NN)
    {
      make_set(i);
    }
  }
  for (int i = 0; i < XX.size(); i++)
  {
    if(a[XX[i]] == NN && a[YY[i]] == NN)
    {
      union_set(XX[i], YY[i]);
    }
  }
  return x - qan;
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
  XX = X;
  YY = Y;
  NN = N;
  if(N <= 50)
  {
    vector<int> G(N, 0);
  vector<int> E(N, N);
  for (int i = 0; i < X.size(); i++)
  {
    v[X[i]].push_back(Y[i]);
    v[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < N; i++)
  {             
    E[i] = 0;
    E[v[i][0]] = 0;
    int x = perform_experiment(E);
    for (int j = 0; j < N; j++)
    {
      E[i] = -1;
      E[v[i][0]] = j;
      int y = perform_experiment(E);
      if(x == y)
      {
        G[i] = j;
        break;;
      }
    }
    E[i] = N;
    E[v[i][0]] = N;
  }
  return G;
  }
  vector<int> harc(N, N);
  vector<int> bi;
  for (int i = 0; i < N; i++)
  {
    harc[i] = -1;
    if(i == 0)
    bi.push_back(1);
    else
    bi.push_back(perform_experimentQ(harc));
  }
  int ne = 1;
  vector<int> ans;
  for (int i = 0; i < N; i++)
  {
    if(i == 0)
    ans.push_back(0);
    else
    {
      int st = 0;
      if(harc[i] != harc[i - 1])
      {
        ans.push_back(ne);
        ne++;
        continue;
      }
      int l = 0, r = i - 2, anss = i - 1;
      while(l <= r)
      {
        int m = (l + r) / 2;
        vector<int> blblb(N, N);
        for (int j = 0; j <= m; j++)
        {
          blblb[j] = -1;
        }
        blblb[i] = -1;
        int x = perform_experimentQ(blblb);
        if(x == harc[m])
        {
          anss= m;
          r = m - 1;
        }
        else
        l = m + 1;
      }
      ans.push_back(ans[anss]);
    }
  }
  return ans;
}

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