Submission #1091779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091779		MMihalev	Rail (IOI14_rail)	C++14	22 / 100	40 ms	616 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;
int pos0;
bool checkdist(int pos,int type,int idx,int realdist)
{
    if(pos>1e6)return 0;
    if(L.count(pos) or R.count(pos))return 0;
    return 1;

    int curdist=1e9;

    if(pos>pos0)
    {
        if(type==2)curdist=pos-pos0;
        else
        {
            auto it=R.upper_bound(pos);
            if(it!=R.end())
            {
                curdist=2*(*it)-pos-pos0;
            }
        }
    }
    else
    {
        auto it=R.upper_bound(pos0);
        if(it!=R.end())
        {
            if(type==1)
            {
                curdist=2*(*it)-pos0-pos;
            }
            else
            {
                auto it2=L.lower_bound(pos);
                if(it2!=L.begin())
                {
                    --it2;

                    curdist=(*it)-pos0+(*it)-(*it2)+pos-(*it2);
                }
            }
        }
    }

    return (curdist==realdist);
}
void findLocation(int N, int first, int location[], int stype[])
{
    int n=N;
    pos0=first;
    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 rd=v[i].first;
        int ldist=getDistance(lidx,idx);
        int rdist=getDistance(ridx,idx);
        int cnt=0;

        if(location[lidx]+ldist<location[ridx] && checkdist(location[lidx]+ldist,2,idx,rd))
        {
            int db=rdist-(location[ridx]-(location[lidx]+ldist));
            if(db>0 && db%2==0)
            {
                db/=2;

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

                    R.insert(location[idx]);
                    //continue;
                }
            }
        }
        /// ( )i )


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

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

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


        if(location[ridx]-rdist>location[lidx] && checkdist(location[ridx]-rdist,1,idx,rd))
        {
            int db=ldist-(location[ridx]-rdist-location[lidx]);
            if(db>0 && db%2==0)
            {
                db/=2;

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

                    L.insert(location[idx]);
                    //continue;
                }
            }
        }
        /// ( i( )


        if(location[ridx]-rdist<location[lidx] && checkdist(location[ridx]-rdist,1,idx,rd))
        {
            int db=ldist-(location[lidx]-(location[ridx]-rdist));
            if(db>0 && db%2==0)
            {
                db/=2;

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

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

Compilation message (stderr)

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

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