Submission #1242671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242671		mychecksedad	Sphinx's Riddle (IOI24_sphinx)	C++20	57 / 100	265 ms	1440 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
#define cerr if(0) cerr
const int N = 250;

struct Dsu{
  vi s, p;
  Dsu(int n){
    s.resize(n, 1);
    p.resize(n);
    for(int i = 0; i < n; ++i) p[i] = i;
  }
  int find(int v){
    if(p[v] == v) return v;
    return p[v] = find(p[v]);
  }
  void merge(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v){
      if(s[u] > s[v]) swap(u, v);
      s[v] += s[u];
      p[u] = v;
    }
  }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rn(int l, int r){
  return uniform_int_distribution<int>(l,r)(rng);
}

bitset<N> IS[N];
vi g[N];
int n;
int ask(vi E){
  return perform_experiment(E);
}

void eras(vi &v, int x){
  for(int j = 0; j < (int) v.size(); ++j){
    if(v[j] == x){
      v.erase(v.begin() + j);
      return;
    }
  }
}
int max_case(vi &E){
  int cnt = n;
  Dsu d(n);
  for(int i = 0; i < n; ++i){
    if(E[i] == -1){
      continue;
    }
    for(int j: g[i]){
      if(E[i] == E[j] && d.find(i) != d.find(j)){
        d.merge(i, j);
        --cnt;
      }
    }
  }
  return cnt;
}

bitset<N> any_edge[N];


std::vector<int> find_colours(int nn, std::vector<int> X, std::vector<int> Y) {
  n = nn;
  int m = X.size();
  for(int i = 0; i < n; ++i) g[i].clear(), IS[i] = 0;
  for(int i = 0; i < m; ++i) g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]), any_edge[X[i]][Y[i]] = any_edge[Y[i]][X[i]] = 1;;
  vi col(n, -1);

  int sum = n;  
  vector<vi> COL(n);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      COL[i].pb(j);
      swap(COL[i][j], COL[i][rn(0, j)]);
    }
  }
  int at_most = 0;
  while(sum > 0 ){
    at_most++;
    vi v;
    for(int i = 0; i < n; ++i) if(col[i] == -1) v.pb(i);
    vector<int> E(n, n);
    for(int i = 0; i < (int) v.size(); ++i) swap(v[i], v[rn(0, i)]);


  

    vi search_set;
    vector<pair<vi, int>> who(n, {vi{}, -1});
    for(int i = 0; i < (int) v.size(); ++i){
      int u = v[i];
      if(E[u] == n){
        int cnt = 0;
        for(int j: g[u]){
          if(E[j] == -1) cnt = -N*N;
          else if(E[j] == n) cnt++;
          else if(IS[u][E[j]] == 0){
            ++cnt;
          }
        }
        if(cnt <= 0) continue;
        E[u] = -1;

        search_set.pb(u);

        for(int j : g[u]){
          if(E[j] == n){
            if(COL[u].size()){
              IS[u][COL[u].back()] = 1;
              who[j].ff.pb(u);
              who[j].ss = COL[u].back();
              E[j] = COL[u].back();
              COL[u].pop_back();
            }
          }else if(IS[u][E[j]] == 0){
            IS[u][E[j]] = 1;
            eras(COL[u], E[j]);
            who[j].ff.pb(u);
          }
        }
      }
    }
    if(search_set.empty()){
      continue;
    }
    vi check_set;
    for(int i = 0; i < n; ++i) if(who[i].ff.size()) check_set.pb(i);
    cerr << '\n';
    cerr << '\n';
    int qq = ask(E);

    // what should this guy be if all of them are not good
    int cnt = max_case(E);

    if(qq != cnt){
      cerr << "there is something \n";
      // there is something...
      // we gotta bs
       
      int L = 0; 
      int mx = int(check_set.size());
      while(L < mx){      
        int l = L, r = mx - 2, res = mx - 1;
        while(l <= r){
          int mid = l+r>>1;
          vi EE(n, n);
          for(int x: search_set) if(col[x] == -1) EE[x] = -1;
          for(int i = L; i <= mid; ++i) EE[check_set[i]] = who[check_set[i]].ss;

          int qq = ask(EE);
          int cnt = max_case(EE);
          
          if(qq != cnt){
            res = mid;
            r = mid - 1;
          }else{
            l = mid + 1;
          }
        }
        int node = check_set[res];

        int max_size = int(who[node].ff.size()); 
        int L2 = 0;
        // for(int y: who[node].ff){
        //   vi EE(n, n);
        //   EE[node] = who[node].ss;
        //   EE[y] = -1;
        //   int qq = ask(EE);
        //   int cnt = max_case(EE);
        //   if(qq != cnt){
        //     col[y] = who[node].ss; 
        //   }
        // }
        for(int x: who[node].ff){
          for(int y : who[node].ff){
            if(x != y){
              assert(any_edge[x][y] == 0);
            }
          }
        }
        while(L2 < max_size){
          int lp = L2, rp = max_size - 2, resp = max_size - 1;
          while(lp <= rp){
            vi EE(n, n);
            int mid = lp+rp>>1;
            for(int j = L2; j <= mid; ++j) if(col[who[node].ff[j]] == -1) EE[who[node].ff[j]] = -1;
            EE[node] = who[node].ss;
            int qq = ask(EE);
            int cnt = max_case(EE);
            if(qq != cnt){
              resp = mid;
              rp = mid - 1;
            }else{
              lp = mid + 1;
            }
          }
          L2 = resp + 1;
          int vv = who[node].ff[resp];
          col[vv] = who[node].ss;

          if(L2 == max_size) break;

          vi EE(n, n);
          for(int j = L2; j < max_size; ++j) if(col[who[node].ff[j]] == -1) EE[who[node].ff[j]] = -1;
          EE[node] = who[node].ss;
          int qq = ask(EE);
          int cnt = max_case(EE);
          if(qq == cnt) break;
        }
        L = res + 1;

        if(L == mx) break;

        vi EE(n, n);
        for(int x: search_set) if(col[x] == -1) EE[x] = -1;
        for(int i = L; i < mx; ++i) EE[check_set[i]] = who[check_set[i]].ss;

        int qq = ask(EE);
        int cnt = max_case(EE);
        if(qq == cnt) break;
      }
    }

    sum = 0;
    for(int j = 0; j < n; ++j) sum += col[j] == -1;
  }

  return col;
}

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