Submission #776139

#	Time	Username	Problem	Language	Result	Execution time	Memory
776139		danikoynov	Rail (IOI14_rail)	C++14	0 / 100	96 ms	736 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;
    vector < pair < int, int > > to_add;
    int tm = -1;
 for (int i = 0; i < in_left.size(); i ++)
    {
        if (to_add.size() > 0 && tm != path[in_left[i]])
        {
            for (pair < int, int > v : to_add)
            {
                ftype[v.first] = 1;
                loc[v.first] = v.second;
                leftmost = v.first;
            }
            to_add.clear();
        }
        ///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 << " " << closest << " " << path[ver] << endl;
            cout << tp << " " << leftmost << endl;
            int cur = getDistance(leftmost, ver);
            ///cout << "Dist " << cur << endl;
            if (cur == 2 * (loc[tp] - loc[leftmost]) + (path[ver] - (loc[closest] - loc[leftmost])))
            {
                /**to_add.push_back({ver, loc[closest] - path[leftmost]});
            tm = path[ver];*/
                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;

}

Compilation message (stderr)

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

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