Submission #171167

#	Time	Username	Problem	Language	Result	Execution time	Memory
171167		AlexLuchianov	Rail (IOI14_rail)	C++14	30 / 100	115 ms	2832 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;

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, id) < getcost(pos, id)){
      int x = location[last2] - getcost(last2, id);
      int y = (getcost(0, id) + x + location[0]) / 2;
      if(getcost(0, id) == (x - location[0]) + 2 * (y - 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';
      }
    } else {
      int x = location[last1] + getcost(last1, id);
      int y = (x + location[pos] - getcost(pos, id)) / 2;
      if(getcost(pos, id) == (location[pos] - x) + 2 * (x - 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';
      }
    }

    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';
  /*
  for(int i = 0; i < N; i++)
    std::cout << stype[i] << " " << location[i] << '\n';
  */
}

/*
1
7
1 1
1 3
1 5
2 2
2 4
2 6
1 0
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:56: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: 0 / 26
• Subtask 4: 0 / 44