Submission #1016825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016825		simona1230	Rail (IOI14_rail)	C++17	0 / 100	199 ms	98740 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;

int l[5001],t[5001];
int d[5001][5001];
int n;
vector<pair<int,int> > v;

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

    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            d[i][j]=d[j][i]=getDistance(i,j);
        }
    }
    //    cout<<vr[i]<<" "<<minn[i]<<endl;


    l[0]=first;
    t[0]=1;

    int minn=1e9,vr1=0;
    for(int i=1; i<n; i++)
    {
        if(d[i][0]<minn)
        {
            minn=d[i][0];
            vr1=i;
        }
    }

    int vr2=0;
    minn=1e9;
    for(int i=0; i<n; i++)
    {
        if(vr1!=i&&d[vr1][i]<minn)
        {
            minn=d[vr1][i];
            vr2=i;
        }
    }
    swap(vr1,vr2);

    l[vr2]=l[0]+d[0][vr2];
    l[vr1]=l[vr2]-1;
    t[vr1]=1;
    t[vr2]=2;
    v.push_back({vr1,vr2});

    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(d[i][j]!=1||i==vr1||j==vr1)continue;

            if(d[vr1][i]<d[vr2][i])
            {
                //cout<<"right"<<endl;
                if(d[vr1][i]<d[vr1][j])
                {
                    t[j]=1;
                    t[i]=2;
                    l[i]=l[vr1]+d[vr1][i];
                    l[j]=l[i]-1;
                    v.push_back({j,i});
                }
                else
                {
                    t[i]=1;
                    t[j]=2;
                    l[j]=l[vr1]+d[vr1][j];
                    l[i]=l[j]-1;
                    v.push_back({i,j});
                }
            }
            else
            {
                //cout<<"left"<<endl;
                if(d[vr2][i]>d[vr2][j])
                {
                    t[j]=1;
                    t[i]=2;
                    l[j]=l[vr2]-d[vr2][j];
                    l[i]=l[j]+1;
                    v.push_back({j,i});
                }
                else
                {
                    t[i]=1;
                    t[j]=2;
                    l[i]=l[vr2]-d[vr2][i];
                    l[j]=l[i]+1;
                    v.push_back({i,j});
                }
            }
        }
    }
    for(int i=0;i<v.size();i++)
    {
        int lf=v[i].first;
        int rt=v[i].second;

        vector<pair<int,int> > curr;
        for(int j=0;j<n;j++)
        {
            if(j==lf||j==rt)continue;
            curr.push_back({d[lf][j],j*10+1});
            curr.push_back({d[rt][j],j*10+2});
        }
        //cout<<l[lf]<<" * "<<l[rt]<<endl;

        sort(curr.begin(),curr.end());
        int cnt=2;
        for(int j=0;j<curr.size();j++)
        {
            if(curr[j].first<=1||curr[j].first>cnt)continue;
            int num=curr[j].second/10;
            int tp=curr[j].second%10;
            if(t[num])continue;
            //cout<<num<<" "<<tp<<endl;
            if(tp==1)t[num]=2,l[num]=d[lf][num]+l[lf];
            else cnt++,t[num]=1,l[num]=l[rt]-d[rt][num];
        }
        //cout<<v[i].first<<" () "<<v[i].second<<endl;
    }

    for(int i=0; i<n; i++)
    {
        location[i]=l[i],stype[i]=t[i];
        //cout<<t[i]<<" "<<l[i]<<endl;
    }
}

Compilation message (stderr)

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

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