Submission #774253

#	Time	Username	Problem	Language	Result	Execution time	Memory
774253		danikoynov	Rail (IOI14_rail)	C++14	30 / 100	349 ms	199732 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
int dist[maxn][maxn], used[maxn];

int ftype[maxn], loc[maxn];
int n;

int get_closest(int vertex)
{
    int closest = -1;
    for (int i = 0; i < n; i ++)
    {
        if (i == vertex)
            continue;
        if (closest == -1 || dist[vertex][closest] > dist[vertex][i])
            closest = i;
    }
    return closest;
}

void action(int lf, int rf)
{
    int closest = -1;
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        if (closest == -1 || dist[lf][closest] > dist[lf][i])
            closest = i;
    }

    if (closest == -1)
        return;

    int left_pos_lf = loc[lf] - (dist[lf][closest] - 2 * dist[lf][rf]);
    int right_pos_lf = loc[lf] + dist[lf][closest];

    int left_pos_rf = loc[rf] - dist[rf][closest];
    int right_pos_rf = loc[rf] + (dist[rf][closest] - 2 * dist[lf][rf]);

    ///cout << "step " << lf << " " << rf << " " << closest << endl;
    ///cout << "lf " << left_pos_lf << " " << right_pos_lf << endl;
    ///cout << "rf " << left_pos_rf << " " << right_pos_rf << endl;
    if (left_pos_lf == left_pos_rf)
    {
        loc[closest] = left_pos_lf;
        ftype[closest] = 1;
        used[closest] = 1;
        int to = get_closest(closest);
        if (to != rf)
        {

            loc[to] = loc[closest] + dist[closest][to];
            ftype[to] = 2;
            used[to] = 1;
            action(closest, to);
        }
        /**for (int i = 0; i < n; i ++)
        {
            if (!used[i] && dist[closest][i] < loc[lf] - loc[closest])
            {
                ///cout << "use left " << i << " " << closest << " " << lf << endl;
                used[i] = 1;
                ftype[i] = 2;
                loc[i] = loc[closest] + dist[closest][i];
            }
        }*/
    }
    else if (right_pos_lf == right_pos_rf)
    {
        loc[closest] = right_pos_lf;
        ftype[closest] = 2;
        used[closest] = 1;
        int to = get_closest(closest);
        if (to != lf)
        {

            loc[to] = loc[closest] - dist[closest][to];
            ftype[to] = 1;
            used[to] = 1;
            action(to, closest);
        }
        /**for (int i = 0; i < n; i ++)
        {
            if (!used[i] && dist[closest][i] < loc[closest] - loc[rf])
            {
                ///cout << "use " << i << endl;
                used[i] = 1;
                ftype[i] = 1;
                loc[i] = loc[closest] - dist[closest][i];
            }
        }*/
    }
    else
    {
        assert(1 == 0);
    }
    /**cout << "------------------" << endl;
        for (int i = 0; i < n; i ++)
            cout << loc[i] << " ";
        cout << endl;
        for (int i = 0; i < n; i ++)
            cout << ftype[i] << " ";
        cout << endl;*/
    action(lf, rf);
}
void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    loc[0] = first;
    ftype[0] = 1;
    used[0] = 1;

    if (N == 1)
        return;

    for (int i = 0; i < N; i ++)
        for (int j = i + 1; j < N; j ++)
        {
            dist[i][j] = dist[j][i] = getDistance(i, j);
        }



    int closest = get_closest(0);
    used[closest] = 1;
    ftype[closest] = 2;
    loc[closest] = loc[0] + dist[closest][0];
    int to = get_closest(closest);
    used[to] = 1;
    ftype[to] = 1;
    loc[to] = loc[closest] - dist[closest][to];

    action(to, closest);

    for (int i = 0; i < N; i ++)
        stype[i] = ftype[i];

    for (int i = 0; i < N; i ++)
        location[i] = loc[i];
}

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