Submission #1241182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241182		MarwenElarbi	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	41 ms	912 KiB

sphinx

#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 5e5+5;

int n;
vector<int> ans;
vector<int> mark(int l,int r,int c,int idx){
  vector<int> cur(n,c);
  int mid=(r+l)/2;
  for (int i = l; i <= mid; ++i)
  {
    cur[i]=(idx ? c : -1);
  }
  for (int i = mid+1; i <= r; ++i)
  {
    cur[i]=(idx ? -1 : c);
  }
  return cur;
}
void daq(int l,int r,vector<int> colors){
  int mid=(r+l)/2;
  if(r-l+1==2){
    if(colors.size()==1){
      daq(l,l,colors);
      daq(r,r,colors);
    }else{
      int a=colors[0];
      int b=colors.back();
      if(perform_experiment(mark(l,mid,a,0)) == 1){
        daq(r,r,{b});
        daq(l,l,{a});
      }else{
        daq(l,l,{b});
        daq(r,r,{a});
      }
    }
    return;
  }else if(r==l){
    ans[l]=colors.back();
    return;
  }
  vector<int> left;
  vector<int> right;
  for(auto u : colors){
    int fir = perform_experiment(mark(l,r,n,0));
    if(perform_experiment(mark(l,r,u,0))<fir) left.push_back(u);
    else if(r-l+1<n) right.push_back(u);
  }
  if(r-l+1==n){
    int fir = perform_experiment(mark(l,r,n,1));
    for(auto u : colors){
      if(perform_experiment(mark(l,r,u,1))<fir){
        right.push_back(u);
      }
    }
  }else{
    int fir = perform_experiment(mark(l,r,n,1));
    for(auto u:left){
      if(perform_experiment(mark(l,r,u,1))<fir) right.push_back(u);
    }
  }
  
  daq(l,mid,left);
  daq(mid+1,r,right);
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  n=N;
  vector<int> colors(N);
  ans.resize(N);
  for (int i = 0; i < N; ++i) colors[i]=i;
  if(n<=50){
    for (int i = 0; i < N; ++i)
    {
      for (int j = 0; j < N; ++j)
      {
        vector<int> tab(N,i);
        tab[j]=-1;
        if(perform_experiment(tab)==1) ans[j]=i;
      }
    }
  }else daq(0,N-1,colors);
  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