Submission #1085503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085503		MMihalev	Rail (IOI14_rail)	C++17	0 / 100	40 ms	608 KiB

rail

#include<iostream>
#include<vector>
#include<algorithm>
#include "rail.h"
using namespace std;
const int MAX_N=5e3+5;
vector<pair<int,int>>leftidx;
vector<pair<int,int>>rightidx;
int lidx;
int ridx;
int n;
int L[MAX_N];
int R[MAX_N];

void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    location[0]=first;
    stype[0]=1;

    vector<pair<int,int>>v;
    for(int i=1;i<n;i++)
    {
        L[i]=getDistance(0,i);
        v.push_back({L[i],i});
    }
    sort(v.begin(),v.end());

    ridx=v[0].second;
    location[ridx]=first+L[ridx];
    stype[ridx]=2;
    v.clear();
    for(int i=0;i<n;i++)
    {
        if(i==ridx)continue;
        if(i!=0)R[i]=getDistance(ridx,i);
        else R[i]=L[ridx];
        v.push_back({R[i],i});
    }
    sort(v.begin(),v.end());

    lidx=v[0].second;
    location[lidx]=location[ridx]-R[lidx];
    stype[lidx]=1;
    int minusdist=L[lidx];

    for(int i=0;i<n;i++)
    {
        L[i]-=minusdist;
    }
    ///L, R, lidx, ridx


    for(int i=0;i<n;i++)
    {
        if(i==lidx or i==ridx)continue;

        if(L[i]>R[i])
        {
            leftidx.push_back({L[i],i});
        }
        else rightidx.push_back({R[i],i});
    }
    sort(leftidx.begin(),leftidx.end());
    sort(rightidx.begin(),rightidx.end());
    ///leftidx, rightidx


    for(int type=1;type<=2;type++)
    {
        if(type==1)
        {
            v=leftidx;
            if(v.size()==0)continue;

            int idxsame=v[0].second;
            int distsame=v[0].first;
            location[idxsame]=location[lidx]-(distsame-R[lidx]);
            stype[idxsame]=type;

            for(int i=1;i<v.size();i++)
            {
                int dif=abs(distsame-v[i].first);

                if(dif==getDistance(idxsame,v[i].second))
                {
                    location[v[i].second]=location[idxsame]+dif;
                    stype[v[i].second]=type;
                }
                else
                {
                    location[v[i].second]=location[idxsame]-dif;
                    stype[v[i].second]=type;

                    idxsame=v[i].second;
                    distsame=v[i].first;
                }
            }
        }
        else
        {
            v=rightidx;
            if(v.size()==0)continue;

            int idxsame=v[0].second;
            int distsame=v[0].first;
            stype[idxsame]=type;
            location[idxsame]=location[ridx]+(distsame-R[lidx]);

            for(int i=1;i<v.size();i++)
            {
                int dif=abs(distsame-v[i].first);

                if(dif==getDistance(idxsame,v[i].second))
                {
                    location[v[i].second]=location[idxsame]-dif;
                    stype[v[i].second]=type;
                }
                else
                {
                    location[v[i].second]=location[idxsame]+dif;
                    stype[v[i].second]=type;

                    idxsame=v[i].second;
                    distsame=v[i].first;
                }
            }
        }
    }
}

Compilation message (stderr)

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

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