oj.uz

Submission #776240

# Submission time Handle Problem Language Result Execution time Memory
776240 2023-07-07T13:26:27 Z danikoynov Rail (IOI14_rail) C++14
100 / 100
 53 ms 4488 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 4172 KB Output is correct
2 Correct 45 ms 4212 KB Output is correct
3 Correct 45 ms 4468 KB Output is correct
4 Correct 47 ms 4340 KB Output is correct
5 Correct 53 ms 4344 KB Output is correct
6 Correct 45 ms 4220 KB Output is correct
7 Correct 51 ms 4220 KB Output is correct
8 Correct 53 ms 4340 KB Output is correct
9 Correct 45 ms 4216 KB Output is correct
10 Correct 45 ms 4348 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4184 KB Output is correct
2 Correct 45 ms 4232 KB Output is correct
3 Correct 44 ms 4488 KB Output is correct
4 Correct 53 ms 4356 KB Output is correct
5 Correct 45 ms 4356 KB Output is correct
6 Correct 46 ms 4212 KB Output is correct
7 Correct 46 ms 4216 KB Output is correct
8 Correct 45 ms 4352 KB Output is correct
9 Correct 45 ms 4232 KB Output is correct
10 Correct 45 ms 4344 KB Output is correct
11 Correct 45 ms 4172 KB Output is correct
12 Correct 45 ms 4352 KB Output is correct
13 Correct 46 ms 4304 KB Output is correct
14 Correct 45 ms 4360 KB Output is correct
15 Correct 45 ms 4364 KB Output is correct
16 Correct 46 ms 4484 KB Output is correct
17 Correct 45 ms 4360 KB Output is correct
18 Correct 45 ms 4352 KB Output is correct
19 Correct 45 ms 4344 KB Output is correct
20 Correct 46 ms 4472 KB Output is correct