Submission #989543

#	Time	Username	Problem	Language	Result	Execution time	Memory
989543		12345678	Rail (IOI14_rail)	C++17	30 / 100	45 ms	640 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

int l, r, st;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    vector<pair<int, int>> v;
    vector<int> d;
    for (int i=1; i<N; i++) v.push_back({getDistance(0, i), i});
    sort(v.begin(), v.end());
    l=0, r=st=v[0].second;
    location[r]=first+v[0].first;
    d.push_back(location[r]);
    stype[r]=2;
    for (int i=1; i<v.size(); i++)
    {
        int u=v[i].second;
        int tmp=location[r]-getDistance(r, u), cost=0;
        int dist=getDistance(l, u);
        int cost2=2*(*upper_bound(d.begin(), d.end(), max(tmp, location[l])))-tmp-location[l];
        //cout<<"debug "<<u<<' '<<l<<' '<<location[l]<<' '<<r<<' '<<location[r]<<'\n';
        //cout<<"tmp "<<tmp<<'\n';
        if (tmp<first) cost=location[st]-tmp+location[st]-location[0];
        else cost=*upper_bound(d.begin(), d.end(), tmp)-tmp+*upper_bound(d.begin(), d.end(), tmp)-location[0];
        if (cost==v[i].first&&cost2==dist)
        {
            stype[u]=1;
            location[u]=tmp;
            if (location[u]<location[l]) l=u;
        }
        else
        {
            stype[u]=2;
            location[u]=location[l]+dist;
            d.push_back(location[u]);
            if (location[u]>location[r]) r=u;
        }
    }
}

Compilation message (stderr)

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

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