제출 #417583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417583		benedict0724	철로 (IOI14_rail)	C++17	30 / 100	87 ms	636 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);

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

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