Submission #96961

#	Time	Username	Problem	Language	Result	Execution time	Memory
96961		tincamatei	Towns (IOI15_towns)	C++14	13 / 100	44 ms	4284 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110;
const int MAX_DIST = 1000000;

int hubDistance(int N, int subtask) {
  int c1 = 0, c2, diam1, diam2;

  vector<int> firstDist(N, 0), secondDist(N, 0), diamdist(N, 0);
  vector<int> distC(N, 0), c1c(N, 0), c2c(N, 0);
  vector<int> fr(1+MAX_DIST, 0);

  c1 = -1, diam1 = -1;
  for(int i = 0; i < N; ++i) {
    firstDist[i] = getDistance(0, i);
    if(firstDist[i] > diam1) {
      diam1 = firstDist[i];
      c1 = i;
    }
  }

  diam2 = c2 = -1;
  for(int i = 0; i < N; ++i) {
    secondDist[i] = getDistance(c1, i);
    if(secondDist[i] > diam2) {
      diam2 = secondDist[i];
      c2 = i;
    }

    distC[i] = (firstDist[i] + secondDist[i] - diam1) / 2;
    c1c[i] = firstDist[i] - distC[i];
    c2c[i] = secondDist[i] - distC[i];
    fr[c1c[i]]++;
  }

  int l = 0, r = N;
  for(int i = 0; i <= diam1; ++i) {
    int x;
    r -= fr[i];

    x = max(l, max(r, fr[i]));
    l += fr[i];

    fr[i] = x;
  }

  int rez = 1000000000, centru = 0;

  for(int i = 0; i < N; ++i) {
    int bestdist = max(c2c[i], diam2 - c2c[i]);
    if(bestdist < rez) {
      rez = bestdist;
      centru = c1c[i];
    } else if(bestdist == rez && fr[c1c[i]] > fr[centru])
      centru = c1c[i];
  }

  for(int i = 0; i < N; ++i)
    distC[i] = distC[i] + abs(centru - c1c[i]);

  // Woo wee pot sa fac element majoritar

  vector<int> mlist;
  int bucket = 0, cand;

  for(int i = 0; i < N; ++i) {
    if(mlist.empty())
      mlist.push_back(i);
    else if(getDistance(mlist.back(), i) < distC[mlist.back()] + distC[i])
      bucket++;
    else {
      mlist.push_back(i);
      if(bucket > 0) {
        bucket--;
        mlist.push_back(mlist[mlist.size() - 2]);
      }
    }
  }

  cand = mlist.back();
  while(!mlist.empty()) {
    if(getDistance(mlist.back(), cand) < distC[mlist.back()] + distC[cand]) {
      mlist.pop_back();
      if(!mlist.empty())
        mlist.pop_back();
      else
        ++bucket;
    } else {
      mlist.pop_back();
      if(bucket > 0)
        --bucket;
    }
  }

  if(bucket > 0)
    rez = -rez;
  return rez;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:9:28: warning: unused parameter 'subtask' [-Wunused-parameter]
 int hubDistance(int N, int subtask) {
                            ^~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39