oj.uz

답안 #930899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930899 2024-02-20T16:19:45 Z vjudge1 철로 (IOI14_rail) C++17
100 / 100
 133 ms 197284 KB 
#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;
// }

Compilation message

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 197024 KB Output is correct
2 Correct 120 ms 196820 KB Output is correct
3 Correct 122 ms 196940 KB Output is correct
4 Correct 125 ms 196944 KB Output is correct
5 Correct 122 ms 197028 KB Output is correct
6 Correct 123 ms 196996 KB Output is correct
7 Correct 121 ms 196948 KB Output is correct
8 Correct 117 ms 196796 KB Output is correct
9 Correct 119 ms 196980 KB Output is correct
10 Correct 120 ms 196984 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 196996 KB Output is correct
2 Correct 119 ms 196816 KB Output is correct
3 Correct 118 ms 196944 KB Output is correct
4 Correct 119 ms 196984 KB Output is correct
5 Correct 121 ms 197000 KB Output is correct
6 Correct 125 ms 196948 KB Output is correct
7 Correct 124 ms 196944 KB Output is correct
8 Correct 130 ms 197284 KB Output is correct
9 Correct 120 ms 196928 KB Output is correct
10 Correct 120 ms 196908 KB Output is correct
11 Correct 125 ms 196948 KB Output is correct
12 Correct 123 ms 197000 KB Output is correct
13 Correct 120 ms 196944 KB Output is correct
14 Correct 123 ms 196932 KB Output is correct
15 Correct 118 ms 196944 KB Output is correct
16 Correct 124 ms 197008 KB Output is correct
17 Correct 124 ms 196988 KB Output is correct
18 Correct 122 ms 196988 KB Output is correct
19 Correct 123 ms 196944 KB Output is correct
20 Correct 127 ms 196984 KB Output is correct