Submission #1198935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198935		hengliao	Fun Tour (APIO20_fun)	C++20	21 / 100	70 ms	32956 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;

#define F first 
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
  const int mxN=1e5+5;
  const int LOG=20;
  
  vector<pair<int, int>> v[mxN][2];
  bool done[mxN];
  int d[mxN];
}

vector<int> createFunTour(int n, int q) {
  memset(done, 0, sizeof(done));
  for(int i=1;i<=n;i++){
    d[i]=0;
    int tar=i;
    tar/=2;
    while(tar>0){
      d[i]++;
      tar/=2;
    }
  }
  for(int i=1;i<=n;i++){
    int tar=i/2;
    int pre=i;
    while(tar>0){
      if(pre==2*tar){
        v[tar][0].pb({d[i]-d[tar], i});
      }
      else{
        v[tar][1].pb({d[i]-d[tar], i});
      }
      pre=tar;
      tar/=2;
    }
  }
  int mx=0, idx=0;
  for(int i=1;i<=n;i++){
    if(d[i]>mx){
      mx=d[i];
      idx=i;
    }
  }
  int cur=idx;
  vector<int> ans(n);

  auto f=[&](int it){
    int tar=it/2;
    int pre=it;
    mx=-1, idx=-1;
    for(int i=0;i<2;i++){
      while(!v[it][i].empty() && done[v[it][i].back().S]){
        v[it][i].pop_back();
      }
      if(!v[it][i].empty()){
        if(v[it][i].back().F>mx){
          mx=v[it][i].back().F;
          idx=v[it][i].back().S;
        }
      }
    }
    while(tar>0){
      if(d[it]-d[tar]>mx){
        mx=d[it]-d[tar];
        idx=tar;
      }
      if(pre==2*tar){
        while(!v[tar][1].empty() && done[v[tar][1].back().S]){
          v[tar][1].pop_back();
        }
        if(!v[tar][1].empty()){
          if(d[it]-d[tar]+v[tar][1].back().F>mx){
            mx=d[it]-d[tar]+v[tar][1].back().F;
            idx=v[tar][1].back().S;
          }
        }
      }
      else{
        while(!v[tar][0].empty() && done[v[tar][0].back().S]){
          v[tar][0].pop_back();
        }
        if(!v[tar][0].empty()){
          if(d[it]-d[tar]+v[tar][0].back().F>mx){
            mx=d[it]-d[tar]+v[tar][0].back().F;
            idx=v[tar][0].back().S;
          }
        }
      }
      pre=tar;
      tar/=2;
    }
    return idx;
  };

  for(int rep=0;rep<n;rep++){
    ans[rep]=cur-1;
    done[cur]=1;
    cur=f(cur);
  }
  // for(auto &it:ans){
  //   cout<<it<<' ';
  // }
  // cout<<'\n';
  return ans;
}

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