Submission #930621

#	Time	Username	Problem	Language	Result	Execution time	Memory
930621		vjudge1	철로 (IOI14_rail)	C++17	8 / 100	45 ms	812 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

vector<pii> getAllDists(int v, vector<int> els)
{
    vector<pii> res;
    for (auto el : els)
        res.pb({getDistance(v, el), el});

    return res;
}

vector<int> loc, tp;
int n;

pii doStuff(int v, int T)
{
    vector<pii> vals;
    {
        vector<int> bf;
        for (int i = 0; i < n; ++i)
            if (!tp[i])
                bf.pb(i);
        vals = getAllDists(v, bf);
        sort(vals.begin(), vals.end());
    }

    if (vals.size() == 0)
        return {-1, -1};

    int curClosing = vals[0].s;
    int curD = vals[0].f;
    tp[curClosing] = 2 - T;
    loc[curClosing] = (T ? loc[v] - vals[0].f : loc[v] + vals[0].f);
    for (int i = 1; i < vals.size(); ++i)
    {
        if (vals[i].f > getDistance(curClosing, vals[i].s))
            break;
        curClosing = vals[i].s;
        curD = vals[i].f;
        tp[curClosing] = 2 - T;
        loc[curClosing] = (T ? loc[v] - vals[i].f : loc[v] + vals[i].f);
    }

    return {curClosing, curD};
}

void findLocation(int N, int first, int location[], int stype[])
{
    n = N;
    loc.resize(N);
    tp.resize(N);

    loc[0] = first;
    tp[0] = 1;

    if (N != 1)
    {
        pii closing0 = doStuff(0, 0);
        pii newOpen = doStuff(closing0.f, 1);
        if (newOpen.f != -1 and closing0.s > newOpen.s)
        {
            pii bf = doStuff(newOpen.f, 0);
            if (bf.f != -1)
                doStuff(bf.f, 1);
        }
    }

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

// /* 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 (stderr)

rail.cpp: In function 'std::pair<int, int> doStuff(int, int)':
rail.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < vals.size(); ++i)
      |                     ~~^~~~~~~~~~~~~

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