Submission #430074

#	Time	Username	Problem	Language	Result	Execution time	Memory
430074		Sundavar	Fun Tour (APIO20_fun)	C++14	0 / 100	3 ms	332 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int get(vector<pii>& furthest, int v){
  pii best = {-1, -1};
  int l = 1;
  while(v > 0){
    best = max(best, {(v-1)/2, l});
    if(v&1) best = max(best, {furthest[v+1].first + l + 1, furthest[v+1].second});
    else best = max(best, {furthest[v-1].first + l + 1, furthest[v-1].second});
    l++, v = (v-1)/2;
  }
  return best.second;
}
void rem(vector<pii>& furthest, int v){
  furthest[v] = {-1e9, -1};
  while(v > 0){
    if(v&1) furthest[(v-1)/2] = max(furthest[v], furthest[v+1]);
    else furthest[(v-1)/2] = max(furthest[v], furthest[v-1]);
    furthest[(v-1)/2].first++;
    furthest[(v-1)/2] = max(furthest[(v-1)/2], {0, (v-1)/2});
    v = (v-1)/2;
  }
}
vector<int> createFunTour(int N, int Q) {
  /*if(N <= 500){
    vector<vector<int> > t(N, vector<int>(N));
    pii start = {-1, 0};
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++) t[i][j] = hoursRequired(i,j), start = max(start, {t[i][j], i});
    vector<bool> alive(N, true);
    int poz = start.second;
    vector<int> ans(N, 0);
    for(int x = 0; x < N; x++){
      ans[x] = poz;
      alive[poz] = false;
      pii best = {-1, 0};
      for(int i = 0; i < N; i++)
        if(alive[i]) best = max(best, {t[poz][i], i});
      poz = best.second;
    }
    return ans;
  }*/
  vector<pii> furthest(N, {-1, -1});
  for(int i = 0; i < N; i++){
    int l = 0, v = i;
    furthest[i] = {0,i};
    while(v > 0){
      furthest[(v-1)/2] = max(furthest[(v-1)/2], {++l, i});
      v = (v-1)/2;
    }
  }
  int poz = N-1;
  vector<int> ans(N, 0);
  for(int x = 0; x < N; x++){
    ans[x] = poz;
    int uj = get(furthest, poz);
    rem(furthest, poz);
    poz = uj;
  }
  ans[N-1] = 0;
  return ans;

}

/*int main(){
  int N;
  cin>>N;
  vector<int> a = createFunTour(N, -1);
  for(int& b : a) cout<<b<<" ";
  cout<<"\n";

}*/

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