제출 #930899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930899		vjudge1	철로 (IOI14_rail)	C++17	100 / 100	133 ms	197284 KiB

rail

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

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long

vector<vector<long long>> dists;
vector<long long> loc, tp, shortest;
int n;
// int C = 0;

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    loc.resize(N);
    tp.resize(N);
    dists.resize(N, vector<long long>(N));
    shortest.resize(N, 2e9 + 10);
    loc[0] = first;
    tp[0] = 1;

    vector<int> dist0(N);
    vector<pair<long long, long long>> vals0;
    for (long long i = 1; i < n; ++i)
    {
        vals0.pb({getDistance(0, i), i});
        dist0[i] = vals0.back().f;
    }
    sort(all(vals0));

    if (N != 1)
    {
        long long closing = vals0.begin()->s;
        tp[closing] = 2;
        loc[closing] = loc[0] + vals0.begin()->f;
        long long distBetween = vals0.begin()->f;
        vector<long long> distC(n);
        vector<pair<long long, long long>> valsC;

        for (long long i = 1; i < n; ++i)
            if (i != closing)
            {
                distC[i] = getDistance(closing, i);
                valsC.pb({distC[i], i});
            }
        sort(all(valsC));

        {
            // long long lastOpening = min(distBetween, valsC[0].f) == distBetween ? 0LL : valsC[0].s, lastClosing = closing;
            long long lastOpening = 0;
            vector<ll> openingBrackets;
            openingBrackets.pb(0);

            for (auto [dist, el] : valsC)
            {
                if (dist0[el] == distC[el] + distBetween)
                    if (dist < distBetween)
                    {
                        openingBrackets.pb(el);
                        tp[el] = 1;
                        loc[el] = loc[closing] - dist;
                    }
                    else
                    {
                        long long X = getDistance(lastOpening, el);
                        bool found = false;
                        for (auto cur : openingBrackets)
                            if (distC[el] == distC[cur] + (X - (loc[cur] - loc[lastOpening])) and (X - (loc[cur] - loc[lastOpening])) > 0)
                                found = true;
                        if (found)
                        {
                            tp[el] = 2;
                            loc[el] = loc[lastOpening] + X;
                        }
                        else
                        {
                            openingBrackets.pb(el);
                            tp[el] = 1;
                            loc[el] = loc[closing] - distC[el];
                            lastOpening = el;
                        }
                    }
            }
        }

        {
            long long lastClosing = closing;
            vector<ll> closingBrackets;
            closingBrackets.pb(closing);

            for (auto [dist, el] : valsC)
            {
                if (!tp[el])
                {
                    long long X = getDistance(lastClosing, el);
                    bool found = false;
                    for (auto cur : closingBrackets)
                        if (dist0[el] == dist0[cur] + (X - (loc[lastClosing] - loc[cur])) and (X - (loc[lastClosing] - loc[cur])) > 0)
                            found = true;
                    if (found)
                    {
                        tp[el] = 1;
                        loc[el] = loc[lastClosing] - X;
                    }
                    else
                    {
                        closingBrackets.pb(el);
                        tp[el] = 2;
                        loc[el] = loc[0] + dist0[el];
                        lastClosing = el;
                    }
                }
            }
        }
    }

    for (long long i = 0; i < n; ++i)
    {
        location[i] = loc[i];
        stype[i] = tp[i];
        // cout << stype[i] << " " << location[i] << " " << i << "!\n";
    }
}

// /* This is sample grader for the contestant */

// #include <unistd.h>
// #include <stdlib.h>
// #include <stdio.h>
// #include <string.h>
// #include <assert.h>
// #include "rail.h"

// typedef struct Station
// {
//     int index;
//     int type;
//     int location;
//     int L, R;
// } STATION;
// long long cnt;
// static int S, SUBTASK;
// static STATION stations[10004];

// int cmp_fun_1(const void *a, const void *b)
// {
//     STATION c, d;
//     c = *(STATION *)(a);
//     d = *(STATION *)(b);
//     return c.location < d.location ? -1 : 1;
// }

// int cmp_fun_2(const void *a, const void *b)
// {
//     STATION c, d;
//     c = *(STATION *)(a);
//     d = *(STATION *)(b);
//     return c.index < d.index ? -1 : 1;
// }

// void now_I_want_to_getLR()
// {
//     int now = stations[S - 1].index, i;
//     for (i = S - 2; i >= 0; i--)
//     {
//         stations[i].R = now;
//         if (stations[i].type == 2)
//             now = stations[i].index;
//     }
//     now = stations[0].index;
//     for (i = 1; i < S; i++)
//     {
//         stations[i].L = now;
//         if (stations[i].type == 1)
//             now = stations[i].index;
//     }
// }

// int getDistance(int x, int y)
// {
//     cnt++;
//     if (x == y)
//         return 0;
//     if (x < 0 || x >= S || y < 0 || y >= S)
//         return -1;
//     if (stations[x].location > stations[y].location)
//     {
//         int tmp = x;
//         x = y;
//         y = tmp;
//     }
//     int ret = 0;
//     if (stations[x].type == 1 && stations[y].type == 1)
//     {
//         ret = stations[stations[y].R].location - stations[x].location + stations[stations[y].R].location - stations[y].location;
//     }
//     else if (stations[x].type == 1 && stations[y].type == 2)
//     {
//         ret = stations[y].location - stations[x].location;
//     }
//     else if (stations[x].type == 2 && stations[y].type == 2)
//     {
//         ret = stations[x].location - stations[stations[x].L].location + stations[y].location - stations[stations[x].L].location;
//     }
//     else if (stations[x].type == 2 && stations[y].type == 1)
//     {
//         ret = stations[x].location - stations[stations[x].L].location + stations[stations[y].R].location - stations[stations[x].L].location + stations[stations[y].R].location - stations[y].location;
//     }
//     return ret;
// }

// void getInput()
// {
//     int g;
//     g = scanf("%d", &SUBTASK);
//     g = scanf("%d", &S);
//     int s;
//     for (s = 0; s < S; s++)
//     {
//         int type, location;
//         g = scanf(" %d %d", &type, &location);
//         stations[s].index = s;
//         stations[s].location = location;
//         stations[s].type = type;
//         stations[s].L = -1;
//         stations[s].R = -1;
//     }
//     qsort(stations, S, sizeof(STATION), cmp_fun_1);
//     now_I_want_to_getLR();
//     qsort(stations, S, sizeof(STATION), cmp_fun_2);
// }

// int serverGetStationNumber()
// {
//     return S;
// }

// int serverGetSubtaskNumber()
// {
//     return SUBTASK;
// }

// int serverGetFirstStationLocation()
// {
//     return stations[0].location;
// }

// int main()
// {
//     int i;
//     getInput();
//     cnt = 0;

//     int location[10005];
//     int type[10005];
//     int ok = 1;
//     findLocation(S, serverGetFirstStationLocation(), location, type);
//     if (SUBTASK == 3 && cnt > S * (S - 1))
//         ok = 0;
//     if (SUBTASK == 4 && cnt > 3 * (S - 1))
//         ok = 0;

//     for (i = 0; i < S; i++)
//         if (type[i] != stations[i].type || location[i] != stations[i].location)
//             ok = 0;
//     if (ok == 0)
//         printf("Incorrect");
//     else
//         printf("Correct");
//     return 0;
// }

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

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:62:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   62 |                 if (dist0[el] == distC[el] + distBetween)
      |                    ^

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