Submission #1043552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043552		deera	Rail (IOI14_rail)	C++14	0 / 100	190 ms	98648 KiB

rail

// ioi 2014 
// Day 1: Rail

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

void findLocation(int N, int first, int location[], int stype[])
{
    vector<vector<int>> dist(N, vector<int>(N, 0));
    vector<pair<int, int>> closest(N, {0, INT_MAX});
    
    for(int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int d = dist[i][j] = dist[j][i] = getDistance(i, j);

            if (closest[i].second > d) {
                closest[i].second = d;
                closest[i].first = j;
            } 

            if (closest[j].second > d) {
                closest[j].second = d;
                closest[j].first = i;
            }
        }
    }

    set<tuple<int, int, int>> pills;
    tuple<int, int, int> prime;

    for (int i = 0; i < closest.size(); i++) {
        if (i < closest[i].first) {
            pills.insert({i, closest[i].first, closest[i].second});
        }

        if (i == 0) {
            prime = {i, closest[i].first, closest[i].second};
        }
    }

    pair<int, int> x = {0, first};
    pair<int, int> y = {get<1>(prime), get<2>(prime) + first};

    for (tuple<int, int, int> pill: pills) {
        int a, b, d;
        tie(a, b, d) = pill;

        // case 1
        // x = a and y = b
        if (x.first == a and y.first == b) {
            location[a] = x.second;
            location[b] = y.second;
            stype[a] = 1;
            stype[b] = 2;
        }

        // case 2
        // x = a
        else if (x.first == a) {
            location[b] = x.second + d;
            stype[b] = 2;
        }

        // case 3
        // y = b
        else if (y.first == b) {
            location[a] = y.second - d;
            stype[a] = 1;
        }

        // case 4
        // x is closer to b than y is closer to a
        // hence a, b is right of x, y
        else if (dist[x.first][b] < dist[y.first][a]) {
            location[b] = x.second + dist[x.first][b];
            location[a] = location[b] - d;
            stype[a] = 1;
            stype[b] = 2;
        }

        // case 5
        // y is closer to a than x is closer to b
        // hence a, b is left of x, y
        else {
            location[a] = y.second - dist[y.first][a];
            location[b] = location[a] + d;
            stype[a] = 1;
            stype[b] = 2;
        }
    } 
}

Compilation message (stderr)

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

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