Submission #785283

#	Time	Username	Problem	Language	Result	Execution time	Memory
785283		Hanksburger	Rail (IOI14_rail)	C++17	100 / 100	52 ms	4436 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int x[1000005], res1[5005], res2[5005];
vector<pair<int, int> > v, w;
void findLocation(int n, int k, int a[], int b[])
{
    a[0]=k;
    b[0]=1;
    x[a[0]]=b[0];
    if (n==1)
        return;
    int ind, mn=1e9, cur=0;
    for (int i=1; i<n; i++)
    {
        res1[i]=getDistance(0, i);
        if (mn>res1[i])
        {
            mn=res1[i];
            ind=i;
        }
    }
    res2[0]=res1[ind];
    a[ind]=a[0]+res1[ind];
    b[ind]=2;
    x[a[ind]]=b[ind];
    for (int i=1; i<n; i++)
    {
        if (i==ind)
            continue;
        res2[i]=getDistance(ind, i);
        if (res1[i]==res1[ind]+res2[i])
        {
            if (res2[i]<res1[ind])
            {
                a[i]=a[ind]-res2[i];
                b[i]=1;
                x[a[i]]=b[i];
            }
            else
                v.push_back({res2[i], i});
        }
        else
            w.push_back({res1[i], i});
    }
    sort(v.begin(), v.end());
    sort(w.begin(), w.end());
    for (int i=0; i<v.size(); i++)
    {
        int u=v[i].second;
        int res=getDistance(cur, u);
        if (x[a[cur]+(res2[cur]+res-res2[u])/2]==1)
        {
            a[u]=a[cur]+res;
            b[u]=2;
        }
        else
        {
            a[u]=a[ind]-res2[u];
            b[u]=1;
            cur=u;
        }
        x[a[u]]=b[u];
    }
    cur=ind;
    for (int i=0; i<w.size(); i++)
    {
        int u=w[i].second;
        int res=getDistance(cur, u);
        if (x[a[cur]-(res1[cur]+res-res1[u])/2]==2)
        {
            a[u]=a[cur]-res;
            b[u]=1;
        }
        else
        {
            a[u]=a[0]+res1[u];
            b[u]=2;
            cur=u;
        }
        x[a[u]]=b[u];
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0; i<v.size(); i++)
      |                   ~^~~~~~~~~
rail.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0; i<w.size(); i++)
      |                   ~^~~~~~~~~
rail.cpp:23:21: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     res2[0]=res1[ind];
      |             ~~~~~~~~^

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