Submission #774005

#	Time	Username	Problem	Language	Result	Execution time	Memory
774005		boris_mihov	Rail (IOI14_rail)	C++17	30 / 100	44 ms	476 KiB

rail

#include "rail.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
int distA[MAXN];
int distB[MAXN];
std::vector <int> cPos;
std::vector <int> dPos;
std::vector <std::pair <int,int>> cQuery;
int myDist(int u, int v)
{
    return getDistance(u - 1, v - 1);
}

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    for (int i = 2 ; i <= n ; ++i)
    {
        distA[i] = myDist(1, i);
    }

    location[0] = first;
    stype[0] = 1;

    int minIdx = 2;
    for (int i = 3 ; i <= n ; ++i)
    {
        assert(distA[i] != distA[minIdx]);
        if (distA[i] < distA[minIdx])
        {
            minIdx = i;
        }
    }

    location[minIdx - 1] = first + distA[minIdx];
    stype[minIdx - 1] = 2;

    for (int i = 2 ; i <= n ; ++i)
    {
        if (i == minIdx)
        {
            continue;
        }

        distB[i] = myDist(minIdx, i);
    }

    for (int i = 2 ; i <= n ; ++i)
    {
        if (i == minIdx)
        {
            continue;
        }

        if (distA[i] == distB[i] + location[minIdx - 1] - location[0])
        {
            // assert(distB[i] != distA[i] + location[minIdx - 1] - location[0]);
            stype[i - 1] = 1;
            location[i - 1] = location[minIdx - 1] - distB[i];
            cPos.push_back(location[i - 1]);
        }

        // if (distB[i] == distA[i] + location[minIdx - 1] - location[0])
        // {
        //     stype[i - 1] = 2;
        //     location[i - 1] = distA[i] + location[0];
        // }
    }

    cPos.push_back(location[0]);
    std::sort(cPos.begin(), cPos.end());

    for (int i = 2 ; i <= n ; ++i)
    {
        if (i == minIdx)
        {
            continue;
        }

        if (distB[i] == distA[i] + location[minIdx - 1] + location[0] - 2 * cPos.back())
        {
            assert(stype[i - 1] == 0);
            stype[i - 1] = 2;
            location[i - 1] = distA[i] + location[0];
        }
    }

    int maxIdx = minIdx - 1;
    minIdx = 0;

    for (int i = 0 ; i < n ; ++i)
    {
        if (stype[i] == 2)
        {
            dPos.push_back(location[i]);
        }

        if (stype[i] == 1 && location[i] < location[minIdx])
        {
            minIdx = i;
        }

        if (stype[i] == 2 && location[i] > location[maxIdx])
        {
            maxIdx = i;
        }
    }

    std::sort(cPos.begin(), cPos.end());
    std::sort(dPos.begin(), dPos.end());

    bool wasIN = false;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (stype[i - 1] == 0)
        {
            wasIN = true;
            // assert((distA[i] == distB[i] + dPos[0] - location[0]) ^ (distB[i] == distA[i] + location[0] - 2 * cPos.back() + dPos[0]));
            if ((distA[i] == distB[i] + dPos[0] - location[0]))
            {
                stype[i - 1] = 2;
                location[i - 1] = getDistance(minIdx, i - 1) + cPos[0];
            } else if (distB[i] == distA[i] + location[0] - 2 * cPos.back() + dPos[0])
            {
                stype[i - 1] = 1;
                location[i - 1] = dPos[0] - getDistance(maxIdx, i - 1);
            } else
            {
                assert(false);
            }
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:121:10: warning: variable 'wasIN' set but not used [-Wunused-but-set-variable]
  121 |     bool wasIN = false;
      |          ^~~~~

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