Submission #417591

#	Time	Username	Problem	Language	Result	Execution time	Memory
417591		benedict0724	Rail (IOI14_rail)	C++17	30 / 100	95 ms	584 KiB

rail

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

using namespace std;

int sp[5002], dist[5002];
bool U[5002];
priority_queue<pair<int, int>> pq;
vector<int> C, D;

void findLocation(int N, int first, int location[], int stype[])
{
    for(int i=1;i<N;i++) dist[i] = getDistance(0, i);
    for(int i=1;i<N;i++) pq.push({-dist[i], i});

    int l = 0, r = pq.top().second;
    stype[0] = 1;
    stype[r] = 2;
    location[0] = first;
    location[r] = first - pq.top().first;
    C.push_back(location[0]);
    D.push_back(location[r]);
    pq.pop();
    for(int i=2;i<N;i++)
    {
        int nxt = pq.top().second, d = -pq.top().first;
        pq.pop();
        int ld = getDistance(l, nxt);
        int rd = getDistance(r, nxt);

        int rt = 10000000;
        for(int j : D) if(max(location[r] - rd, location[0]) < j) rt = min(rt, j);

        int sd = 2 * rt - location[0] - (location[r] - rd);

        int kt = 10000000;
        for(int j : D) if(max(location[r] - rd, location[l]) < j) kt = min(kt, j);
        int kd = 2 * kt - location[l] - (location[r] - rd);

        if(sd == d)
        {
            stype[nxt] = 1;
            location[nxt] = location[r] - rd;
            C.push_back(location[nxt]);
            if(location[l] > location[nxt]) l = nxt;
        }
        else
        {
            stype[nxt] = 2;
            location[nxt] = location[l] + ld;
            D.push_back(location[nxt]);
            if(location[r] < location[nxt]) r = nxt;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:38:13: warning: unused variable 'kd' [-Wunused-variable]
   38 |         int kd = 2 * kt - location[l] - (location[r] - rd);
      |             ^~

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