oj.uz

Submission #96957

# Submission time Handle Problem Language Result Execution time Memory
96957 2019-02-13T00:49:27 Z tincamatei Towns (IOI15_towns) C++14
25 / 100
 49 ms 4412 KB 
#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.empty() &&
       getDistance(mlist.back(), i) == distC[mlist.back()] + distC[i])) {
      mlist.push_back(i);
      if(bucket > 0) {
        mlist.push_back(mlist[mlist.size() - 2]);
        bucket--;
      }
    } else
      ++bucket;
  }

  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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4284 KB Output is correct
2 Correct 30 ms 4284 KB Output is correct
3 Correct 5 ms 4224 KB Output is correct
4 Correct 34 ms 4284 KB Output is correct
5 Correct 31 ms 4156 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4412 KB Output is correct
2 Correct 32 ms 4236 KB Output is correct
3 Correct 35 ms 4396 KB Output is correct
4 Correct 40 ms 4352 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 4284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 4308 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 4284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 4284 KB Output isn't correct
2 Halted 0 ms 0 KB -