Submission #1085558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085558		MMihalev	Rail (IOI14_rail)	C++14	30 / 100	169 ms	98688 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];
int dist[MAX_N][MAX_N];
int q=0;
void add()
{
    if(q==n*(n-1)/2)while(1);
    q++;
}

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);add();dist[0][i]=dist[i][0]=L[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);add();dist[ridx][i]=dist[i][ridx]=R[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);add();dist[lidx][0]=dist[0][lidx]=L[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 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,g;
                for(auto [distsame,idxsame]:same)
                {
                    dif=v[i].first-distsame;
                    if(dist[idxsame][v[i].second]!=0)g=dist[idxsame][v[i].second];
                    else
                    {
                        g=getDistance(idxsame,v[i].second);
                        dist[idxsame][v[i].second]=dist[v[i].second][idxsame]=g;
                    }
                    if(dif==g)
                    {
                        ok=1;
                        id=idxsame;
                        break;
                    }
                }
                if(ok)
                {
                    location[v[i].second]=location[id]+dif;
                    stype[v[i].second]=type;
                }
                else
                {
                    location[v[i].second]=location[same.back().second]-(abs(v[i].first-same.back().first));
                    stype[v[i].second]=type;
                    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,g;
                for(auto [distsame,idxsame]:same)
                {
                    dif=v[i].first-distsame;
                    if(dist[idxsame][v[i].second]!=0)g=dist[idxsame][v[i].second];
                    else
                    {
                        g=getDistance(idxsame,v[i].second);
                        dist[idxsame][v[i].second]=dist[v[i].second][idxsame]=g;
                    }
                    if(dif==g)
                    {
                        ok=1;
                        id=idxsame;
                        break;
                    }
                }
                if(ok)
                {
                    location[v[i].second]=location[id]-dif;
                    stype[v[i].second]=type;
                }
                else
                {
                    location[v[i].second]=location[same.back().second]+(abs(v[i].first-same.back().first));
                    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:94: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]
   94 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
rail.cpp:99:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |                 for(auto [distsame,idxsame]:same)
      |                          ^
rail.cpp:140: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]
  140 |             for(int i=1;i<v.size();i++)
      |                         ~^~~~~~~~~
rail.cpp:145:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  145 |                 for(auto [distsame,idxsame]:same)
      |                          ^

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