Submission #1091527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091527		MMihalev	Rail (IOI14_rail)	C++14	56 / 100	73 ms	856 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];

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

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

                    if(dif==getDistance(idxsame,v[i].second))
                    {
                        ok=1;
                        id=idxsame;
                        break;

                    }
                }
                if(ok)
                {
                    location[v[i].second]=location[id]+dif;
                    stype[v[i].second]=2;
                }
                else
                {
                    location[v[i].second]=location[same.back().second]-(abs(v[i].first-same.back().first));;
                    stype[v[i].second]=1;
                    same.push_back(v[i]);
                }
            }
        }
        else
        {
            v=rightidx;
            if(v.size()==0)continue;

            int idxsam=v[0].second;
            int distsam=v[0].first;
            stype[idxsam]=type;
            location[idxsam]=location[ridx]+(distsam-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;
                int id;
                for(auto [distsame,idxsame]:same)
                {
                    dif=v[i].first-distsame;

                    if(dif==getDistance(idxsame,v[i].second))
                    {
                        id=idxsame;
                        ok=1;
                        break;
                    }
                }
                if(ok)
                {
                    location[v[i].second]=location[id]-dif;
                    stype[v[i].second]=1;
                }
                else
                {
                    location[v[i].second]=location[same.back().second]+(abs(v[i].first-same.back().first));
                    stype[v[i].second]=2;
                    same.push_back(v[i]);
                }
            }
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:86: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]
   86 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
rail.cpp:91:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |                 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:133:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |                 for(auto [distsame,idxsame]:same)
      |                          ^

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