제출 #776107

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

rail

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

using namespace std;

const int maxn = 5010;

int loc[maxn], ftype[maxn], dist[maxn], path[maxn];
int used[maxn];

bool cmp_dist(int v, int u)
{
    return dist[v] < dist[u];
}

bool cmp_path(int v, int u)
{
    return path[v] < path[u];
}

void findLocation(int N, int first, int location[], int stype[])
{
    loc[0] = first;
    ftype[0] = 1;

    int closest = -1;
    for (int i = 0; i < N; i ++)
    {
        if (i != 0)
        {
            dist[i] = getDistance(i, 0);
            if (closest == - 1 || dist[i] < dist[closest])
                closest = i;
        }
    }

    vector < int > in_left, in_right;

    loc[closest] = loc[0] + dist[closest];
    ftype[closest] = 2;
    for (int i = 0; i < N; i ++)
    {
        if (i == 0 || i == closest)
            continue;
        path[i] = getDistance(i, closest);
        if (dist[i] == dist[closest] + path[i])
        {
            if (path[i] < loc[closest] - loc[0])
            {
                ftype[i] = 1;
                loc[i] = loc[closest] - path[i];
            }
            else
                in_left.push_back(i);
        }
        else
            in_right.push_back(i);
    }


    sort(in_right.begin(), in_right.end(), cmp_dist);
    int rightmost = closest;
    for (int i = 0; i < in_right.size(); i ++)
    {
        int ver = in_right[i];
        /**if (rightmost == -1)
        {
            rightmost = ver;
            ftype[rightmost] = 2;
            loc[rightmost] = loc[0] + dist[rightmost];
        }
        else*/
        {
            int tp = 0;
            for (int j = 0; j < N; j ++)
            {
                if (ftype[j] == 1 && loc[j] > loc[tp])
                    tp = j;
            }

            int cur = getDistance(rightmost, ver);
            if (cur == 2 * (loc[rightmost] - loc[tp]) + (dist[ver] - (loc[rightmost] - loc[0])))
            {
                rightmost = ver;
                ftype[rightmost] = 2;
                loc[rightmost] = loc[0] + dist[rightmost];
            }
            else
            {
                ftype[ver] = 1;
                loc[ver] = loc[rightmost] - cur;
            }
        }
    }

    sort(in_left.begin(), in_left.end(), cmp_path);

    int leftmost = 0;
 for (int i = 0; i < in_left.size(); i ++)
    {
        ///cout << "in_left " << in_left[i] << endl;
        int ver = in_left[i];
        /**if (rightmost == -1)
        {
            rightmost = ver;
            ftype[rightmost] = 2;
            loc[rightmost] = loc[0] + dist[rightmost];
        }
        else*/
        {
            int tp = closest;
            for (int j = 0; j < N; j ++)
            {
                if (ftype[j] == 2 && loc[j] < loc[tp])
                    tp = j;
            }
            ///cout << "step " << ver << endl;
            ///cout << tp << " " << leftmost << endl;
            int cur = getDistance(leftmost, ver);
            if (cur == 2 * (loc[tp] - loc[leftmost]) + (path[ver] - (loc[closest] - loc[leftmost])))
            {
                leftmost = ver;
                ftype[leftmost] = 1;
                loc[leftmost] = loc[closest] - path[leftmost];
            }
            else
            {
                ftype[ver] = 2;
                loc[ver] = loc[leftmost] + cur;
            }
        }
    }
    for (int i = 0; i < N; i ++)
        location[i] = loc[i];
    for (int i = 0; i < N; i ++)
        stype[i] = ftype[i];

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

}

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

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < in_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
rail.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = 0; i < in_left.size(); i ++)
      |                  ~~^~~~~~~~~~~~~~~~

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