Submission #1210096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210096		trimkus	스핑크스 (IOI24_sphinx)	C++20	36 / 100	31 ms	444 KiB

sphinx

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

vector<int> E;
int N;
const int MAXN = 250;
int p[MAXN];
bool vis[MAXN];
vector<int> adj[MAXN];
vector<int> adj1[MAXN];
int parity[MAXN];
int get(int x) {
  return (p[x] < 0 ? x : p[x] = get(p[x]));
}
int color(int x) {
  return (E[x] >= 0 ? E[x] + N : get(x));
}



int expected() {
  int cnt = 1;
  for (int i = 1; i < N; ++i) {
    if (E[i] != E[i - 1]) {
      cnt++;
    }
  }
  return cnt;
}


std::vector<int> find_colours(int _N, std::vector<int> X, std::vector<int> Y) {
  N = _N;
  E = vector<int>(N);
  vector<int> F(N, -1);
  vector<bool> online(N);
  for (int i = 0; i < (int)X.size(); ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < N; ++i) {
    p[i] = -1;
  }
  for (int par = 0; par < 2; ++par) {
    for (int i = 0; i < N; ++i) {
      while (true) {
        for (int j = 0; j < N; ++j) {
          if ((j & 1) == par || F[j] != -1) {
            E[j] = i;
          } else {
            E[j] = -1;
          }
        }
        if (expected() == perform_experiment(E)) {
          break;
        }
        vector<int> pool;
        for (int j = 0; j < N; ++j) {
          if ((j & 1) == par ^ 1 && F[j] == -1) {
            pool.push_back(j);
          }
        }
        int left = 0, right = (int)pool.size() - 1;
        while (left < right) {
          int mid = (left + right) / 2;
          for (int j = 0; j < N; ++j) {
            E[j] = i;
          }
          for (int j = 0; j <= mid; ++j) {
            E[pool[j]] = -1;
          }
          if (expected() == perform_experiment(E)) {
            left = mid + 1;
          } else {
            right = mid;
          }
        }
        F[pool[right]] = i;
      }
    }
  }
  return F;
}

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