제출 #1244547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244547		AlperenT_	스핑크스 (IOI24_sphinx)	C++20	10 / 100	170 ms	1252 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 500 + 100 , inf = 1e9 , mod = 998244353;
vector <int> vec[maxn] , G[maxn] ;
int par[maxn] , mark[maxn] , n;
vector <int> y;int ig ;
void dfs(int v){
  mark[v] =1 ;
  for(int u : G[v]){
    if(y[u] == ig && mark[u] == 0)dfs(u);
  }
} 
int que(vector <int> x , int igg = n){
  ig = igg ;
  int sm =perform_experiment(x);
  y =x; 
  rep(i ,0 , n-1){
    mark[i] =0 ; 
  }
  rep(i ,0, n-1){
    if(mark[i] ==0 && x[i] == ig){
      dfs(i) ;
      sm-- ;
    }
  }
  return sm ; 
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
  n = N; 
  rep(i , 0 ,sz(X)-1){
    G[X[i]].pb(Y[i]);
    G[Y[i]].pb(X[i]); 
  }
  rep(i , 0 ,n-1)vec[i].pb(i);
  vector<int> az ;
  rep(i , 0 , n-1){
    while(1){
      vector <int> e ;
      rep(j , 0 ,n-1){
        if(j > i){
          e.pb(n);
          continue ;
        }
        e.pb(-1);
      }
      if(que(e) == 1 + sz(az)){
        az.pb(i) ;
        break ;
      }
      int l =-1 , r = sz(az)-1;
      while(r-l > 1){
        int m = (l+r)/2 ;
        vector <int> e ;
        rep(i , 0 ,n-1)e.pb(n) ;
        e[i] = -1 ;
        rep(i , 0 ,m){
          int x = az[i] ;
          for(int y : vec[x]){
            e[y] = -1 ;
          }
        }
        if(que(e) == 1 + (m+1)){
          l = m; 
        }else{
          r = m ;
        }
      }
      par[az[r]] = i;
      for(int x : vec[az[r]])vec[i].pb(x) ;
      vector <int> az2 ;
      rep(i , 0 ,sz(az)-1){
        if(i == r)continue;
        az2.pb(az[i]);
      }
      az = az2 ;
    }
  }
  int cnt = 0;
  vector <int> ans ;
  rep(i , 0 ,n-1)ans.pb(0);
  vector <int> rem ; 
  rep(i , 0, n-1)rem.pb(1) ;
  for(int x : az){
    vector <int> e;int col = 0 ; 
    rep(j , 0 ,n-1){
      if(rem[j]==1){
        vector <int> s; 
        rep(i , 0 , n-1){
          s.pb(j) ;
        }
        s[x]= -1;
        if(que(s , j) == 1){
          
        }else{
          col = j;
          break ;
        }
      }
    }
    for(int y : vec[x]){
      ans[y] = col ;
    }
  }
  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