제출 #773839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773839		danikoynov	Rail (IOI14_rail)	C++14	30 / 100	3058 ms	98588 KiB

rail

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

using namespace std;

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

int lf, rf, ftype[maxn], loc[maxn];
    int n;
void extend_rf(int to)
{
    used[to] = 1;
    ftype[to] = 2;
    loc[to] = loc[lf] + dist[lf][to];
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        if (dist[to][i] < dist[to][lf])
        {
            ftype[i] = 1;
            used[i] = 1;
            loc[i] = loc[to] - dist[to][i];
        }
    }
    rf = to;
}

void extend_lf(int to)
{
    used[to] = 1;
    ftype[to] = 1;
    loc[to] = loc[rf] - dist[rf][to];
    for (int i = 0; i < n; i ++)
    {
        if (used[i])
            continue;
        if (dist[to][i] < dist[to][rf])
        {
            ftype[i] = 2;
            used[i] = 1;
            loc[i] = loc[to] + dist[to][i];
        }
    }
    lf = to;
}

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 = -1;
    for (int i = 1; i < N; i ++)
    {
        if (closest == -1 || dist[0][closest] > dist[0][i])
            closest = i;
    }


    lf = 0;
    rf = 0;
    extend_rf(closest);

    int last = 0;
    while(true)
    {
        /**int cnt = 0;
        for (int i = 0; i < N; i ++)
            cnt += used[i];
        assert(cnt != last);
        last = cnt;*/

        bool done = true;
        for (int i = 0; i < N; i ++)
            if (!used[i])
            {
                done = false;
                break;
            }

        if (done)
            break;

        int ft = -1;
        for (int i = 0; i < N; i ++)
        {
            if (!used[i] || ftype[i] == 1)
                continue;
            if (ft == - 1 || loc[i] < loc[ft])
                ft = i;
        }
        int df = -1;
        for (int i = 0; i < N; i ++)
        {
            if (!used[i] || ftype[i] == 2)
                continue;
            if (loc[i] < loc[ft] && (df == -1 || loc[i] > loc[df]))
                df = i;
        }

        int closest = -1;

        for (int i = 0; i < N; i ++)
        {
            if (used[i])
                continue;

            if (closest == -1 ||
                    dist[df][closest] > dist[df][i])
                closest = i;

            ///if (closest_rf == -1 ||
              ///      dist[rf][closest_rf] > dist[rf][i])
               // closest_rf = i;
        }



        int lf_loc = loc[df] - (dist[df][closest] - 2 * dist[df][ft]);
        int rf_loc = loc[df] + dist[df][closest];

        /**int df = -1;
        for (int i = 0; i < N; i ++)
        {
            if (!used[i] || ftype[i] == 2)
            continue;
            if (df == -1 || loc[i] > loc[df])
                df = i;
        }*/
        ///assert(loc[lf])
        int st_loc = loc[ft] - dist[ft][closest];
        int pt_loc = loc[ft] + (dist[ft][closest] - 2 * dist[ft][df]);
        ///cout << "step " << lf << " " << ft << " " << st_loc << " " << rf_loc << endl;
        if (st_loc == lf_loc)
            extend_lf(closest);
        else
        if (rf_loc == pt_loc)
            extend_rf(closest);
        else
        {
            ///assert(1 == 0);
        }
    }

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

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

    ///for (int i = 0; i < N; i ++)
       /// cout << location[i] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:77:9: warning: unused variable 'last' [-Wunused-variable]
   77 |     int last = 0;
      |         ^~~~

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