Submission #171168

#	Time	Username	Problem	Language	Result	Execution time	Memory
171168		AlexLuchianov	Rail (IOI14_rail)	C++14	100 / 100	156 ms	2812 KiB

rail

#include "rail.h"
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>

std::ofstream out ("data.out");

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 5000;
int const inf = 1000000000;

std::map<std::pair<int,int>, int> cost;

int getcost(int x, int y){
  if(cost.find({x, y}) == cost.end())
    cost[{y, x}] = cost[{x, y}] = getDistance(x, y);
  return cost[{x, y}];
}

struct Train{
  int id;
  int dist;
  bool operator < (Train const &a) const{
    return dist < a.dist;
  }
};

std::map<int,char> type;

int mark[1 + nmax];

void findLocation(int N, int first, int location[], int stype[])
{
  int pos = 1;
  for(int i = 1;i < N; i++)
    if(getcost(0, i) < getcost(0, pos))
      pos = i;
  location[0] = first;
  stype[0] = 1;
  type[location[0]] = 'C';
  location[pos] = first + getcost(0, pos);
  stype[pos] = 2;
  type[location[pos]] = 'D';

  std::vector<Train> v;
  for(int i = 1; i < N; i++)
    if(i != pos)
      v.push_back({i, getcost(0, i)});
  std::sort(v.begin(), v.end());

  int last1 = 0, last2 = pos;

  for(int i = 0; i < v.size(); i++){
    int id = v[i].id;
    if(getcost(0, pos) + getcost(pos, id) != getcost(0, id)){
      int x = location[last2] - getcost(last2, id);
      int y = (getcost(0, id) + x + location[0]) / 2;
      if(getcost(0, id) == (2 * y - location[0] - x) && type[y] == 'D'){
        location[id] = x;
        stype[id] = 1;
        type[location[id]] = 'C';
      } else {
        location[id] = location[0] + getcost(0, id);
        stype[id] = 2;
        type[location[id]] = 'D';
      }
      mark[id] = 1;
    } else {
      int x = location[last1] + getcost(last1, id);
      int y = (x + location[pos] - getcost(pos, id)) / 2;
      if(getcost(pos, id) == (x + location[pos] - 2 * y) && type[y] == 'C'){
        location[id] = x;
        stype[id] = 2;
        type[location[id]] = 'D';
      } else {
        location[id] = location[pos] - getcost(pos, id);
        stype[id] = 1;
        type[location[id]] = 'C';
      }
      mark[id] = 2;
    }

    if(stype[id] == 2 && location[last2] < location[id])
      last2 = id;
    if(stype[id] == 1 && location[id] < location[last1])
      last1 = id;
    //std::cout << id << " " << location[id] << " " << stype[id] << '\n';
  }
  //std::cout << '\n';
  //*

  //std::cout << 0 << " " << location[0] << '\n';
  //std::cout << pos << " " << location[pos] << '\n';
  /*
  for(int i = 0; i < N; i++)
    out << stype[i] << " " << location[i] << " " << mark[i] << " " << getcost(0, i) << " " << getcost(pos, i) <<  '\n';
  //*/
}

/*
1
5
1 1
1 2
2 6
2 7
2 8
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~

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