Submission #1177742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177742		madamadam3	Sphinx's Riddle (IOI24_sphinx)	C++20	26.50 / 100	10 ms	3728 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]);
  }

  bool path = M == N - 1 && adj[0] == set<int>({1}) && adj[N - 1] == set<int>({N - 2});
  for (int i = 1; i < N - 1; i++) {
    path = path && adj[i] == set<int>({i - 1, i + 1});
  }
  
  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; 
  } else if (path) {
    G[0] = 0;
    G[1] = queryTwo(0, 1, -1, -1) == 2 ? G[0] : 1 - G[0];

    for (int i = 2; i < N - 1; i++) {
      G[i] = queryTwo(i - 1, i, -1, -1) == 3 ? G[i - 1] : 1 - G[i - 1];
    }

    G[N - 1] = queryTwo(N - 2, N - 1, -1, -1) == 2 ? G[N - 2] : 1 - G[N - 2];

    return G;
  } else if (M == (N * (N - 1) / 2)) {
    
    return G;
  }



  return G;
}

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