Submission #1085535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085535		MMihalev	Rail (IOI14_rail)	C++14	0 / 100	65 ms	716 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;
        R[i]=getDistance(ridx,i);
        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]-2*R[lidx];

    for(int i=0;i<n;i++)
    {
        //if(i!=0)L[i]-=minusdist;
        //else L[i]=getDistance(0,lidx);
        L[i]=getDistance(lidx,i);
    }
    for(int i=0;i<n;i++)
    {
        //if(i!=0)L[i]-=minusdist;
        //else L[i]=getDistance(0,lidx);
        R[i]=getDistance(ridx,i);
    }
    ///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-2*R[lidx]);
            stype[idxsame]=type;
            vector<pair<int,int>>same;
            same.push_back(v[0]);

            for(int i=1;i<v.size();i++)
            {
                bool ok=0;
                int dif;
                for(auto [distsame,idxsame]:same)
                {
                    dif=abs(distsame-v[i].first);

                    if(dif==getDistance(idxsame,v[i].second))
                    {
                        ok=1;
                        break;
                    }
                }
                if(ok)
                {
                    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;
                    same.push_back(v[i]);
                }
            }
        }
        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-2*R[lidx]);
            vector<pair<int,int>>same;
            same.push_back(v[0]);

            for(int i=1;i<v.size();i++)
            {
                bool ok=0;
                int dif;
                for(auto [distsame,idxsame]:same)
                {
                    dif=abs(distsame-v[i].first);

                    if(dif==getDistance(idxsame,v[i].second))
                    {
                        ok=1;
                        break;
                    }
                }
                if(ok)
                {
                    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;
                    same.push_back(v[i]);
                }
            }
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:89: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]
   89 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
rail.cpp:93:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |                 for(auto [distsame,idxsame]:same)
      |                          ^
rail.cpp:128: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]
  128 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
rail.cpp:132:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |                 for(auto [distsame,idxsame]:same)
      |                          ^
rail.cpp:110:60: warning: 'dif' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |                     location[v[i].second]=location[idxsame]-dif;
      |                                           ~~~~~~~~~~~~~~~~~^~~~

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