Submission #556042

#	Time	Username	Problem	Language	Result	Execution time	Memory
556042		MilosMilutinovic	Rail (IOI14_rail)	C++14	100 / 100	101 ms	32128 KiB

rail

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

using namespace std;

const int MAX = 5005;

int dist[MAX][MAX];

int ask(int i, int j) {
  if (i == j) {
    return 0;
  }
  if (i > j) {
    swap(i, j);
  }
  if (!dist[i][j]) {
    dist[i][j] = getDistance(i, j);
  }
  return dist[i][j];
}

void findLocation(int n, int first, int location[], int stype[]) {
  map<int, int> mp;
  location[0] = first;
  stype[0] = 1;
  mp[location[0]] = 1;
  if (n == 1) {
    return;
  }
  vector<int> d0(n);
  for (int i = 1; i < n; i++) {
    d0[i] = ask(0, i);
  }
  int idx = 1;
  for (int i = 2; i < n; i++) {
    if (d0[i] < d0[idx]) {
      idx = i;
    }
  }
  location[idx] = first + d0[idx];
  stype[idx] = 2;
  mp[location[idx]] = 2;
  vector<int> dx(n);
  for (int i = 0; i < n; i++) {
    dx[i] = ask(idx, i);
  }
  vector<int> l;
  vector<int> r;
  for (int i = 1; i < n; i++) {
    if (i == idx) {
      continue;
    }
    if (d0[i] == ask(0, idx) + dx[i]) {
      if (d0[idx] > dx[i]) {
        location[i] = location[idx] - dx[i];
        stype[i] = 1;
        mp[location[i]] = 1;
      } else {
        l.push_back(i);
      }
    } else {
      r.push_back(i);
    }
  }
  sort(l.begin(), l.end(), [&](int i, int j) {
    return dx[i] < dx[j];
  });
  sort(r.begin(), r.end(), [&](int i, int j) {
    return d0[i] < d0[j];
  });
  int R = idx;
  for (int id = 0; id < r.size(); id++) {
    int i = r[id];
    int d = (d0[R] + ask(R, i) - ask(0, i)) / 2;
    if (mp[location[R] - d] == 2) {
      location[i] = location[R] - ask(R, i);
      stype[i] = 1;
      mp[location[i]] = 1;
    } else {
      location[i] = location[0] + ask(0, i);
      stype[i] = 2;
      mp[location[i]] = 2;
      R = i;
    }
  }
  int L = 0;
  for (int id = 0; id < l.size(); id++) {
    int i = l[id];
    int d = (dx[L] + ask(L, i) - ask(idx, i)) / 2;
    if (mp[location[L] + d] == 1) {
      location[i] = location[L] + ask(L, i);
      stype[i] = 2;
      mp[location[i]] = 2;
    } else {
      location[i] = location[idx] - ask(idx, i);
      stype[i] = 1;
      mp[location[i]] = 1;
      L = i;
    }
  }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int id = 0; id < r.size(); id++) {
      |                    ~~~^~~~~~~~~~
rail.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int id = 0; id < l.size(); id++) {
      |                    ~~~^~~~~~~~~~

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