Submission #1025732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025732		NeroZein	Rail (IOI14_rail)	C++17	100 / 100	43 ms	856 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[]) {
  vector<int> d0(N);
  for (int i = 1; i < N; ++i) {
    d0[i] = getDistance(0, i); 
  }
  int id = 0, mn = INT_MAX;
  for (int i = 1; i < N; ++i) {
    if (d0[i] < mn) {
      id = i;
      mn = d0[i];
    }
  }
  stype[0] = 1; 
  location[0] = first;
  stype[id] = 2; 
  location[id] = location[0] + d0[id];
  vector<int> did(N);
  did[0] = d0[id];
  vector<int> left, right;
  for (int i = 1; i < N; ++i) {
    if (i == id) {
      continue; 
    }
    did[i] = getDistance(id, i);
    if (d0[i] == d0[id] + did[i]) {
      left.push_back(i);
    } else {
      right.push_back(i);
    }
  }
  sort(right.begin(), right.end(), [&](int i, int j) {
    return d0[i] < d0[j];
  });
  set<int> f;
  int last = id; 
  f.insert(location[id]);
  for (int i : right) {
    int d = getDistance(last, i);
    int z = abs(d0[i] - d0[last] - d) / 2;
    if (f.count(location[last] - z)) {
      stype[i] = 1; 
      location[i] = location[last] - d; 
    } else {
      stype[i] = 2;
      location[i] = location[0] + d0[i];
      last = i;
      f.insert(location[i]);
    }
  }
  last = 0; 
  f.clear();
  f.insert(location[0]);
  sort(left.begin(), left.end(), [&](int i, int j) {
    return did[i] < did[j];
  });
  for (int i : left) {
    int d = getDistance(last, i); 
    int z = abs(did[i] - did[last] - d) / 2; 
    if (f.count(location[last] + z)) {
      stype[i] = 2;
      location[i] = location[last] + d; 
    } else {
      stype[i] = 1; 
      location[i] = location[id] - did[i];
      last = i;
      f.insert(location[i]); 
    }
  }
}

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