제출 #1310993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310993		M_W_13	철로 (IOI14_rail)	C++20	30 / 100	41 ms	588 KiB

rail

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int INF = 1e9;

void findLocation(int n, int first, int location[], int stype[])
{
    vector<pii> vec;
    location[0] = first;
    stype[0] = 1;
    if (n == 1) return ;
    for (int i = 1; i < n; i++) {
        int x = getDistance(0, i);
        vec.pb({x, i});
    }
    sort(all(vec));
    int x = 0;
    int y = vec[0].nd;
    location[y] = location[x] + vec[0].st;
    stype[y] = 2;
    vector<int> znane;
    znane.pb(0);
    znane.pb(y);
    int sz = vec.size();
    for (int it = 1; it < sz; it++) {
        pii p = vec[it];
        int i = p.nd;
        int a = getDistance(x, i);
        int b = getDistance(y, i);
        int px = location[x];
        int py = location[y];
        int dla = INF;
        int dlb = INF;
        for (auto v: znane) {
            if (stype[v] == 1) {
                if (location[v] >= (px + a)) continue;
                dlb = min(dlb, py - location[v] + px + a - location[v]);
            }
            else {
                if (location[v] <= (py - b)) continue;
                dla = min(dla, location[v] - px + location[v] - (py - b));
            }
        }
        znane.pb(i);
        if (dlb == b) {
            location[i] = px + a;
            stype[i] = 2;
            if ((px + a) > py) {
                y = i;
            }
        }
        else {
            location[i] = py - b;
            stype[i] = 1;
            if ((py - b) < px) {
                x = i;
            }
        }
        // cout << "i = " << i << " location = " << location[i] << " stype = " << stype[i] << " x = " << x << " y = " << y << '\n';
    }
}

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