Submission #776240

#	Time	Username	Problem	Language	Result	Execution time	Memory
776240		danikoynov	Rail (IOI14_rail)	C++14	100 / 100	53 ms	4488 KiB

rail

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

using namespace std;

const int maxn = 2e6 + 10;

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];
}

int marked[maxn];

void findLocation(int N, int first, int location[], int stype[])
{
    loc[0] = first;
    ftype[0] = 1;
    marked[first] = 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;
    marked[loc[closest]] = 2;
    path[0] = dist[closest];
    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;
                marked[loc[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];
        int cur = getDistance(rightmost, ver);
        int dz = dist[ver] - dist[rightmost] - cur;
        dz = (-dz / 2);
        if (loc[rightmost] - dz >= 0 && marked[loc[rightmost] - dz] == 2)
        {
            loc[ver] = loc[rightmost] - cur;
            ftype[ver] = 1;
            marked[loc[ver]] = 1;
        }
        else
        {
            loc[ver] = loc[0] + dist[ver];
            ftype[ver] = 2;
            marked[loc[ver]] = 2;
            rightmost = ver;
        }
    }

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

    int leftmost = 0;
    for (int i = 0; i < in_left.size(); i ++)
    {
        int ver = in_left[i];
        int cur = getDistance(leftmost, ver);

        int dz = path[ver] - path[leftmost] - cur;
        dz = (- dz / 2);
        //cout << "---------------------------" << endl;
        //cout << "step " << ver << " " << leftmost  << " " << dz << endl;
        //cout << "path " << path[ver] << " " << path[leftmost] << " " << getDistance(ver, leftmost) << endl;
        if (marked[loc[leftmost] + dz] == 1)
        {
            loc[ver] = loc[leftmost] + cur;
            ftype[ver] = 2;
            marked[loc[ver]] = 2;
        }
        else
        {
            loc[ver] = loc[closest] - path[ver];
            ftype[ver] = 1;
            marked[loc[ver]] = 1;
            leftmost = ver;

        }
    }
    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:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < in_right.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
rail.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < in_left.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~

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