Submission #429512

#	Time	Username	Problem	Language	Result	Execution time	Memory
429512		TLP39	Rail (IOI14_rail)	C++14	100 / 100	102 ms	4584 KiB

rail

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

int n;
pair<int,int> a[5003];
int cl;
int dist[2][5003];
vector<int> v[2];
int station[1000001];
int f[2];
void findLocation(int N, int start, int location[], int stype[])
{
    for(int i=0;i<1000001;i++) station[i]=-1;
    n=N;
    location[0]=start;
    stype[0]=1;
    station[start]=0;
    if(n==1) return;
    for(int i=1;i<n;i++)
    {
        a[i-1]={getDistance(0,i),i};
        dist[0][i]=a[i-1].first;
    }
    sort(a,a+n-1);
    cl=a[0].second;
    location[cl]=start+a[0].first;
    stype[cl]=2;
    station[location[cl]]=cl;
    for(int i=0;i<n-1;i++)
    {
        if(a[i].second==cl)
        {
            dist[1][cl]=0;
            continue;
        }
        dist[1][a[i].second]=getDistance(cl,a[i].second);
        if(dist[0][a[i].second]-dist[1][a[i].second]==a[0].first)
        {
            if(dist[1][a[i].second]<a[0].first)
            {
                location[a[i].second]=location[cl]-dist[1][a[i].second];
                stype[a[i].second]=1;
                station[location[a[i].second]]=a[i].second;
            }
            else
            {
                v[0].push_back(a[i].second);
            }
        }
        else
        {
            v[1].push_back(a[i].second);
        }
    }
    int turn;
    if(!v[0].empty())
    {
        int dist0;
        location[v[0][0]]=location[cl]-dist[1][v[0][0]];
        stype[v[0][0]]=1;
        station[location[v[0][0]]]=v[0][0];
        f[0]=v[0][0];
        for(int i=1;i<v[0].size();i++)
        {
            dist0=getDistance(f[0],v[0][i]);
            turn=(location[f[0]]+location[cl]+dist0-dist[1][v[0][i]])>>1;
            if(station[turn]>-1 && stype[station[turn]]==1)
            {
                location[v[0][i]]=location[f[0]]+dist0;
                stype[v[0][i]]=2;
                station[location[v[0][i]]]=v[0][i];
            }
            else
            {
                location[v[0][i]]=location[cl]-dist[1][v[0][i]];
                stype[v[0][i]]=1;
                station[location[v[0][i]]]=v[0][i];
                f[0]=v[0][i];
            }
        }
    }

    if(!v[1].empty())
    {
        int dist1;
        location[v[1][0]]=location[0]+dist[0][v[1][0]];
        stype[v[1][0]]=2;
        station[location[v[1][0]]]=v[1][0];
        f[1]=v[1][0];
        for(int i=1;i<v[1].size();i++)
        {
            dist1=getDistance(f[1],v[1][i]);
            turn=(location[f[1]]+location[0]-dist1+dist[0][v[1][i]])>>1;
            if(station[turn]>-1 && stype[station[turn]]==2)
            {
                location[v[1][i]]=location[f[1]]-dist1;
                stype[v[1][i]]=1;
                station[location[v[1][i]]]=v[1][i];
            }
            else
            {
                location[v[1][i]]=location[0]+dist[0][v[1][i]];
                stype[v[1][i]]=2;
                station[location[v[1][i]]]=v[1][i];
                f[1]=v[1][i];
            }
        }
    }
    return;
}

Compilation message (stderr)

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

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