Submission #1177712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177712		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	10 ms	3588 KiB

sphinx

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

using namespace std;

typedef long long ll;
using vi = vector<int>; 
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

void trace_vec(vi &inp) {
  for (auto &el : inp) cout << el << " ";
  cout << "\n";
}

int N, M;
vector<set<int>> adj;
vi G;

int queryTwo(int a, int b, int colourA, int colourB) {
  vi E(N, N);
  E[a] = colourA;
  E[b] = colourB;

  return perform_experiment(E);
}

void findColour(int a) {
  if (G[a] != -1) return;

  int neighbour = *adj[a].begin();

  int b2 = queryTwo(a, neighbour, 0, 0);
  int baseline = queryTwo(a, neighbour, -1, -1);
  bool same = baseline == b2;

  for (int colour = 0; colour < N; colour++) {
    int x1 = queryTwo(a, neighbour, colour, -1);
    int x2 = queryTwo(a, neighbour, -1, colour);

    if (same && b2 == x1) {
      G[a] = G[neighbour] = colour;
      return;
    }

    if (!same && x1 == b2) {
      G[neighbour] = colour;
    }
    if (!same && x2 == b2) {
      G[a] = colour;
    }
  }
}

void findFrom(int a, int b) {
  if (G[a] == -1) return;
  if (G[b] != -1) return;
  if (adj[a].count(b) == 0) return;

  int baseline = queryTwo(a, b, -1, -1);

  for (int colour = 0; colour < N; colour++) {
    int x = queryTwo(a, b, colour, -1);
    if (x < baseline) {
      G[b] = colour;
      break;
    } else if (x > baseline) {
      G[b] = G[a];
      break;
    }
  }
}

vi find_colours(int _N, vi X, vi Y) {
  N = _N, M = (int) X.size();

  adj.assign(N, set<int>());
  for (int i = 0; i < M; i++) {
    adj[X[i]].insert(Y[i]);
    adj[Y[i]].insert(X[i]);
  }
  
  G.assign(N, -1);

  if (N == 2) { // 3/100 pts
    findColour(0);
    return G;
  } else if (N <= 50) {
    set<int> vis;
    queue<int> q;

    q.push(0);
    findColour(0);

    while (!q.empty()) {
      int cur = q.front();
      q.pop();

      // cout << "visited " << cur << "\n";

      vis.insert(cur);

      for (int v : adj[cur]) {
        if (vis.count(v)) continue;
        findFrom(cur, v);
        q.push(v);
      }

      // cout << "colour is: " << G[cur] << "\n";
    }

    return G; 
  }


  return G;
}

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