Submission #1202876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202876		ackhava	Fun Tour (APIO20_fun)	C++20	47 / 100	96 ms	15296 KiB

fun

#include "fun.h"
#pragma GCC optimize "O3,unroll-loops"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(v) begin(v), end(v)
#define REP(i,o,n) for(int i=o;i<n;i++)
using namespace std;

int centroid(int N){
  int ans=0;
  int vis=N;
  REP(i,1,N){
    int c=attractionsBehind(0, i);
    if(vis >= c && c >= ((N+1)/2))ans=i,vis=c;
  }
  return ans;
}

int mem[100100];

int subtree(vector<int> direct, int center, int i){
  if(find(all(direct),i)!=direct.end())return find(all(direct),i)-direct.begin();
  REP(x,0,direct.size()-1){
    if((hoursRequired(direct[x], i)+1)==mem[i])return x;
  }
  return direct.size()-1;
}

std::vector<int> createFunTour(int N, int Q) {
  int center = centroid(N);
  vector<int> direct;
  vector<deque<pair<int,int>>> vec;
  REP(i,0,N)mem[i]=hoursRequired(center,i);
  REP(i,0,N){
    if(mem[i]==1)direct.pb(i),vec.emplace_back();
  }
  REP(i,0,N){
    if(mem[i])vec[subtree(direct,center,i)].pb({mem[i],i});
  }
  REP(i,0,vec.size()){
    sort(all(vec[i]));
    reverse(all(vec[i]));
  }
  vector<int> ans;
  int lastidx=-1;
  while(vec.size()){
    pair<int,int> mx = {-1,-1};
    REP(i,0,vec.size())if(vec[i].size() && i!=lastidx)mx=max(mx,vec[i][0]);
    REP(i,0,vec.size())if(vec[i].size() && vec[i][0]==mx){lastidx=i;break;}
    if(mx.fi == -1)break;
    vec[lastidx].pop_front();
    ans.pb(mx.se);

    int large=-1;
    int sz=0;
    REP(i,0,vec.size()){
      sz+=vec[i].size();
    }
    REP(i,0,vec.size()){
      if(vec[i].size()*2 == sz)large=i;
    }
    if(vec.size()==3 && large!=-1){
      deque<pair<int,int>> lgx,smx;
      for(auto i:vec[large])lgx.pb(i);
      REP(i,0,3)if(i!=large)for(auto j:vec[i])smx.pb(j);
      sort(all(lgx));reverse(all(lgx));
      sort(all(smx));reverse(all(smx));
      if(lastidx==large)lastidx=0;
      else lastidx=1;
      vec.clear();
      vec.pb(lgx);
      vec.pb(smx);
    }
  }
  ans.pb(center);
  // cerr<<"! ";
  // for(auto i:ans)cerr<<i<<" ";
  // cerr<<endl;
  return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34