Submission #1091534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091534		MMihalev	Rail (IOI14_rail)	C++14	30 / 100	42 ms	644 KiB

rail

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include "rail.h"
using namespace std;
set<int>L;
set<int>R;
int lidx,ridx;
void findLocation(int N, int first, int location[], int stype[])
{
    int n=N;
    location[0]=first;
    stype[0]=1;


    lidx=0;
    vector<pair<int,int>>v;
    for(int i=1;i<n;i++)
    {
        v.push_back({getDistance(0,i),i});
    }
    sort(v.begin(),v.end());
    ridx=v[0].second;
    location[ridx]=location[0]+v[0].first;
    stype[ridx]=2;

    L.insert(location[0]);
    R.insert(location[ridx]);

    for(int i=1;i<v.size();i++)
    {
        int idx=v[i].second;
        int ldist=getDistance(lidx,idx);
        int rdist=getDistance(ridx,idx);


        if(location[lidx]+ldist<location[ridx])
        {
            int db=rdist-(location[ridx]-(location[lidx]+ldist));
            if(db%2==0)
            {
                db/=2;

                if(L.count(location[lidx]+ldist-db))
                {
                    location[idx]=location[lidx]+ldist;
                    stype[idx]=2;

                    if(location[idx]>location[ridx])ridx=idx;
                    R.insert(location[idx]);
                    continue;
                }
            }
        }
        /// ( )i )


        if(location[lidx]+ldist>location[ridx])
        {
            int db=rdist-(location[lidx]+ldist-location[ridx]);
            if(db%2==0)
            {
                db/=2;

                if(L.count(location[ridx]-db))
                {
                    location[idx]=location[lidx]+ldist;
                    stype[idx]=2;

                    if(location[idx]>location[ridx])ridx=idx;
                    R.insert(location[idx]);
                    continue;
                }
            }
        }
        /// ( ) )i


        if(location[ridx]-rdist>location[lidx])
        {
            int db=ldist-(location[ridx]-rdist-location[lidx]);
            if(db%2==0)
            {
                db/=2;

                if(R.count(location[ridx]-rdist+db))
                {
                    location[idx]=location[ridx]-rdist;
                    stype[idx]=1;

                    if(location[idx]<location[lidx])lidx=idx;
                    L.insert(location[idx]);
                    continue;
                }
            }
        }
        /// ( i( )


        if(location[ridx]-rdist<location[lidx])
        {
            int db=ldist-(location[lidx]-(location[ridx]-rdist));
            if(db%2==0)
            {
                db/=2;

                if(R.count(location[lidx]+db))
                {
                    location[idx]=location[ridx]-rdist;
                    stype[idx]=1;

                    if(location[idx]<location[lidx])lidx=idx;
                    L.insert(location[idx]);
                    continue;
                }
            }
        }
        /// i( ( )
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31: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]
   31 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~

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