Submission #959653

#	Time	Username	Problem	Language	Result	Execution time	Memory
959653		vjudge1	Rail (IOI14_rail)	C++17	56 / 100	391 ms	98772 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 5e3;

int n, dis[N][N];

void findLocation(int NN, int first, int location[], int stype[]) {
  n = NN;

  for (int i = 0; i < n; i++) {
    dis[i][i] = 0;
    for (int j = i+1; j < n; j++) {
      dis[i][j] = dis[j][i] = getDistance(i, j);
    }
  }

  int x = 1;
  int mn = dis[0][1];
  for (int i = 2; i < n; i++) {
    if (dis[0][i] < mn) {
      mn = dis[0][i];
      x = i;
    }
  }
  stype[0] = 1;
  location[0] = first;
  stype[x] = 2;
  location[x] = first + dis[0][x];

  vector<pair<int, int>> a;
  for (int i = 1; i < n; i++) {
    if (i == x) continue;
    a.push_back(make_pair(dis[0][i], i));
  }
  sort(all(a));
  
  vector<int> l, r;
  r.push_back(x);
  for (int i = 0; i < n-2; i++) {
    int d = a[i].first;
    int idx = a[i].second;

    bool found = 0;

    // es uno de tipo 2 a mi izquierda
    // cojo el primero hacia arriba y luego uno hacia abajo
    for (int& j : l) {
      if (d == dis[0][x] + dis[x][j] + dis[j][idx]) {
        stype[idx] = 2;
        location[idx] = location[j] + dis[j][idx];
        found = 1;
        break;
      }
    }
    if (found) continue;

    // es uno de tipo 1
    // cojo uno hacia arriba
    for (int& j : r) {
      if (d == dis[0][j] + dis[j][idx]) {
        stype[idx] = 1;
        location[idx] = location[j] - dis[j][idx];
        l.push_back(idx);
        found = 1;
        break;
      }
    }
    if (found) continue;


    // es uno nuevo a la derecha
    stype[idx] = 2;
    location[idx] = first + dis[0][idx];
    r.push_back(idx);
  }
}

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