Submission #1001351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001351		abczz	Rail (IOI14_rail)	C++17	30 / 100	39 ms	644 KiB

rail

#include "rail.h"
#include <iostream>
#include <vector>
#include <array>
#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;
  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;
  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) {
        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);
    if (d + A[p] == x) {
      location[y] = a+A[p]-d;
      stype[y] = 1;
    }
    else {
      location[y] = a+x;
      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);
    if (d + B[p] == x) {
      location[y] = b-B[p]+d;
      stype[y] = 2;
    }
    else {
      location[y] = b-x;
      stype[y] = 1;
      tmp = y;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:44: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]
   44 |   for (int i=0; i<U.size(); ++i) {
      |                 ~^~~~~~~~~
rail.cpp:59: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]
   59 |   for (int i=0; i<V.size(); ++i) {
      |                 ~^~~~~~~~~
rail.cpp:22:16: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   b = location[id] = first + mn;
      |                ^~
rail.cpp:48:16: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     if (d + A[p] == x) {
      |             ~~~^

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