Submission #587920

#	Time	Username	Problem	Language	Result	Execution time	Memory
587920		yutabi	Rail (IOI14_rail)	C++14	100 / 100	79 ms	4372 KiB

rail

#include "rail.h"


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


#define pb push_back


typedef pair <int,int> ii;


int left_index=0;

int left_location;

int left_diff[5000];


int right_index;

int right_location;

int right_diff[5000];



vector <ii> left_vals;
vector <ii> right_vals;


int types[1000007];



void findLocation(int N, int first, int location[], int stype[])
{
    left_location=first;

    int mini=300000000;
    
    for(int i=0;i<N;i++)
    {

        if(left_index!=i)
        {
            left_diff[i]=getDistance(left_index,i);


            if(left_diff[i]<mini)
            {
                right_index=i;
                right_location=left_location+left_diff[i];

                mini=left_diff[i];
            }
        }
    }

    types[left_location]=1;
    location[left_index]=left_location;
    stype[left_index]=1;

    types[right_location]=2;
    location[right_index]=right_location;
    stype[right_index]=2;

    for(int i=0;i<N;i++)
    {
        if(right_index!=i)
        {
            right_diff[i]=getDistance(right_index,i);
        }
    }

    for(int i=0;i<N;i++)
    {
        if(i!=left_index && i!=right_index)
        {
            if(right_diff[i]+right_diff[left_index]==left_diff[i])
            {
                if(right_diff[i]<right_diff[left_index])
                {
                    location[i]=right_location-right_diff[i];
                    stype[i]=1;

                    types[right_location-right_diff[i]]=1;
                }

                else
                {
                    left_vals.pb(ii(right_diff[i],i));
                }
            }

            else
            {
                right_vals.pb(ii(left_diff[i],i));
            }
        }
    }

    sort(left_vals.begin(),left_vals.end());



    int leftest_C=-1;

    for(int i=0;i<left_vals.size();i++)
    {
        if(leftest_C==-1)
        {
            leftest_C=left_vals[i].second;

            location[left_vals[i].second]=right_location-left_vals[i].first;
            stype[left_vals[i].second]=1;

            types[right_location-left_vals[i].first]=1;

            continue;
        }

        int res=getDistance(left_vals[i].second,leftest_C);

        if(res==left_vals[i].first+right_diff[leftest_C])
        {
            leftest_C=left_vals[i].second;

            location[left_vals[i].second]=right_location-left_vals[i].first;
            stype[left_vals[i].second]=1;

            types[right_location-right_diff[left_vals[i].second]]=1;

            continue;
        }

        if(types[location[leftest_C]+(res-(left_vals[i].first-right_diff[leftest_C]))/2]==1)
        {
            location[left_vals[i].second]=location[leftest_C]+res;
            stype[left_vals[i].second]=2;

            types[location[leftest_C]+res]=2;
        }

        else
        {
            leftest_C=left_vals[i].second;

            location[left_vals[i].second]=right_location-left_vals[i].first;
            stype[left_vals[i].second]=1;

            types[right_location-right_diff[left_vals[i].second]]=1;

            continue;
        }
    }

    sort(right_vals.begin(),right_vals.end());

    int rightest_D=-1;

    for(int i=0;i<right_vals.size();i++)
    {
        if(rightest_D==-1)
        {
            rightest_D=right_vals[i].second;

            location[right_vals[i].second]=left_location+right_vals[i].first;
            stype[right_vals[i].second]=2;

            types[left_location+right_vals[i].first]=2;

            continue;
        }

        int res=getDistance(right_vals[i].second,rightest_D);

        if(res==right_vals[i].first+left_diff[rightest_D])
        {
            rightest_D=right_vals[i].second;

            location[right_vals[i].second]=left_location+right_vals[i].first;
            stype[right_vals[i].second]=2;

            types[left_location+right_vals[i].first]=2;

            continue;
        }

        if(types[location[rightest_D]-(res-(right_vals[i].first-left_diff[rightest_D]))/2]==2)
        {
            location[right_vals[i].second]=location[rightest_D]-res;
            stype[right_vals[i].second]=1;

            types[location[rightest_D]+res]=1;
        }

        else
        {
            rightest_D=right_vals[i].second;

            location[right_vals[i].second]=left_location+right_vals[i].first;
            stype[right_vals[i].second]=2;

            types[left_location+right_vals[i].first]=2;

            continue;
        }
    }

    return;
}

Compilation message (stderr)

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

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