Submission #964353

#	Time	Username	Problem	Language	Result	Execution time	Memory
964353		efedmrlr	Fun Tour (APIO20_fun)	C++17	100 / 100	173 ms	21024 KiB

fun

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "fun.h"

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n;

int centro = 0;
vector<int> roots;
vector<vector<array<int,2> > > subs;
array<int,2> isMerge() {
  if(subs.size() <= 2) return {-1, -1};
  array<array<int,2> ,3> s;
  REP(i, 3) {
    s[i] = {(int)subs[i].size(), i};
  }
  sort(all(s));
  if(s[2][0] >= s[1][0] + s[0][0]) {
    return {s[1][1], s[0][1]};
  }
  return  {-1, -1};
}

std::vector<int> createFunTour(int N, int Q) {
  n = N;
  int mn = INF;
  for(int i = 1; i<n; i++) {
    int tmp = attractionsBehind(0, i);
    if(tmp * 2 > N) {
      if(mn > tmp) {
        mn = tmp;
        centro = i;
      }
    }
  }
//   cout << "centro:" << centro << endl;
  for(int i = 0; i < n; i++) {
    if(i == centro) continue;
    if(hoursRequired(centro, i) == 1) {
      roots.pb(i);
    }

  }
  subs.assign(roots.size(), vector<array<int, 2> >());
  for(int i = 0; i < n; i++) {
    if(i == centro) continue;
    int d1, d2;
    d1 = hoursRequired(roots[0], i);
    if(roots.size() > 1) {
      d2 = hoursRequired(roots[1], i);
      if(d1 == d2) {
        subs[2].pb({d1 - 1, i});
      }
      else if(d1 > d2) {
        subs[1].pb({d2 + 1, i});
      }
      else {
        subs[0].pb({d1 + 1, i});
      }
    }
    else {
      subs[0].pb({d1 + 1, i});
      continue;
    }
    
  }
  for(int i = 0; i < roots.size(); i++) {
    sort(all(subs[i]));
  }
  vector<int> ret;
  int curp = 0, last = -1;
  int lh = 0;

    auto tmp = isMerge();
    if(tmp[0] > tmp[1]) swap(tmp[0], tmp[1]);
    if(tmp[0] != -1) {
        // cout << "merged" << endl;
        vector<array<int,2> > arr(subs[tmp[0]].size() + subs[tmp[1]].size());
        merge(all(subs[tmp[0]]), all(subs[tmp[1]]), arr.begin());
        swap(subs[tmp[0]], arr);
        swap(subs[tmp[1]], subs[subs.size() - 1]);
        subs.pop_back();
    }
//   for(auto &c : subs) {
//     for(auto &i : c) {
//       cout << i[0] << " " << i[1] << "\n";
//     }
//     cout << "new c" << endl;
//   }
  
  for(int z = 0; z < n - 1; z++) {
    curp = -1;
    if(z != 0 && subs.size() > 2) {
      bool f1 = 1;
      REP(i, 3) {
        if(i == last) continue;
        if(subs[i].back()[0] > lh) {
          f1 = 0;
        }
        
      }
      auto tmp = isMerge();
      if(tmp[0] > tmp[1]) swap(tmp[0], tmp[1]);
      if(f1 && tmp[0] != -1) {
        // cout << "merged" << "\n";
        vector<array<int,2> > arr(subs[tmp[0]].size() + subs[tmp[1]].size());
        merge(all(subs[tmp[0]]), all(subs[tmp[1]]), arr.begin());
        swap(subs[tmp[0]], arr);
        swap(subs[tmp[1]], subs[subs.size() - 1]);
        last = tmp[0];
        subs.pop_back();
      }
    }
    if(subs.size() == 2 && subs[0].size() != subs[1].size()) {
        if(subs[0].size() > subs[1].size()) curp = 0;
        else curp = 1; 
    }
    else {
        for(int i = 0; i < subs.size(); i++) {
        if(i == last) continue;
        
        if(curp == -1 || subs[curp].back()[0] < subs[i].back()[0]) {
            curp = i;
        }
        else if(subs[curp].back()[0] == subs[i].back()[0] && subs[curp].size() < subs[i].size()) {
            curp = i;
        }
        }
    }
    // cout << "curp:" << curp << endl;
    ret.pb(subs[curp].back()[1]);
    lh = subs[curp].back()[0];
    subs[curp].pop_back();
    if(subs[curp].size() == 0) {
      swap(subs[curp], subs[subs.size() - 1]);
      subs.pop_back();
      curp = -1;
    }
    last = curp;
    // cout << ret.back() << endl;
  }
  ret.pb(centro);
//   for(auto c : ret) {
//     cout << c << " ";
//   }
//   cout << endl;
  return ret;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int i = 0; i < roots.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
fun.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int i = 0; i < subs.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

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