Submission #1002156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002156		abczz	Rail (IOI14_rail)	C++17	100 / 100	44 ms	1116 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>
#include <algorithm>
#define ll long long
 
using namespace std;
 
void findLocation(int N, int first, int location[], int stype[])
{
  location[0] = first, stype[0] = 1;
  if (N == 1) return;
  vector <array<ll, 2>> U, V;
  ll A[5000], B[5000], mn = 1e18, id, a = first, b, p, tmp;
  map <ll, ll> mp;
  for (int i=1; i<N; ++i) {
    A[i] = getDistance(0, i);
    if (mn > A[i]) {
      mn = A[i], id = i;
    }
  }
  b = location[id] = first + mn;
  stype[id] = 2;
  mp[a] = 1, mp[b] = 2;
  for (int i=0; i<N; ++i) {
    if (i != id) B[i] = getDistance(id, i);
  }
  for (int i=1; i<N; ++i) {
    if (i == id) continue;
    if (A[i] < B[i] || abs(A[i]-B[i]) != b-a) {
      U.push_back({A[i], i});
    }
    else {
      if (B[i] < mn) {
        mp[b-B[i]] = 1;
        location[i] = b-B[i];
        stype[i] = 1;
        continue;
      }
      V.push_back({B[i], i});
    }
  }
  sort(U.begin(), U.end());
  sort(V.begin(), V.end());
  p = id;
  for (int i=0; i<U.size(); ++i) {
    if (i && U[i][0] != U[i-1][0]) p = tmp;
    auto [x, y] = U[i];
    auto d = getDistance(y, p);
    auto k = (x+d-A[p])/2;
    if (mp[a+x-k] == 2) {
      location[y] = a+x-2*k;
      mp[a+x-2*k] = 1;
      stype[y] = 1;
    }
    else {
      location[y] = a+x;
      mp[a+x] = 2;
      stype[y] = 2;
      tmp = y;
    }
  }
  p = 0;
  for (int i=0; i<V.size(); ++i) {
    if (i && V[i][0] != V[i-1][0]) p = tmp;
    auto [x, y] = V[i];
    auto d = getDistance(y, p);
    auto k = (x+d-B[p])/2;
    if (mp[b-x+k] == 1) {
      location[y] = b-x+2*k;
      mp[b-x+2*k] = 2;
      stype[y] = 2;
    }
    else {
      location[y] = b-x;
      mp[b-x] = 1;
      stype[y] = 1;
      tmp = y;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i=0; i<U.size(); ++i) {
      |                 ~^~~~~~~~~
rail.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
rail.cpp:24:16: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |   b = location[id] = first + mn;
      |                ^~
rail.cpp:52:22: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     auto k = (x+d-A[p])/2;
      |                   ~~~^

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44