Submission #1018231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018231		Andrey	Rail (IOI14_rail)	C++14	30 / 100	49 ms	604 KiB

rail

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

void findLocation(int n, int first, int location[], int stype[])
{
    location[0] = first;
    stype[0] = 1;
    vector<int> dis(n);
    int sm = INT_MAX,p = -1;
    for(int i = 1; i < n; i++) {
        dis[i] = getDistance(0,i);
        if(dis[i] < sm) {
            sm = dis[i];
            p = i;
        }
    }
    location[p] = first+sm;
    stype[p] = 2;
    vector<pair<int,int>> a(0);
    vector<pair<int,int>> b(0);
    for(int i = 1; i < n; i++) {
        if(i != p) {
            if(getDistance(p,i) < dis[i]) {
                a.push_back({dis[i],i});
            }
            else {
                b.push_back({dis[i],i});
            }
        }
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int p1 = -1;
    for(int i = 0; i < b.size(); i++) {
        if(p1 == -1 || getDistance(p1,b[i].second) >= dis[b[i].second]-dis[p1]) {
            location[b[i].second] = first+dis[b[i].second];
            stype[b[i].second] = 2;
            p1 = b[i].second;
        }
        else {
            location[b[i].second] = first+2*dis[p1]-dis[b[i].second];
            stype[b[i].second] = 1;
        }
    }
    p1 = -1;
    for(int i = 0; i < a.size(); i++) {
        if(p1 == -1 || getDistance(p1,a[i].second) >= dis[a[i].second]-dis[p1]) {
            location[a[i].second] = first-dis[a[i].second]+2*dis[p];
            stype[a[i].second] = 1;
            p1 = a[i].second;
        }
        else {
            location[a[i].second] = first+2*dis[p]-(2*dis[p1]-dis[a[i].second]);
            stype[a[i].second] = 2;
        }
    }
}

Compilation message (stderr)

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

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