제출 #1217918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217918		HappyCapybara	철로 (IOI14_rail)	C++20	0 / 100	34 ms	836 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> d0, dx;

void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;
    if (N == 1) return;
    set<pair<int,int>> cs, ds;
    cs.insert({first, 0});
    d0.resize(N);
    d0[0] = 0;
    for (int i=1; i<N; i++) d0[i] = getDistance(0, i);
    pair<int,int> cl = {pow(10, 7), -1};
    for (int i=1; i<N; i++) cl = min(cl, {d0[i], i});
    int x = cl.second;
    dx.resize(N);
    dx[x] = 0;
    dx[0] = d0[x];
    location[x] = first+d0[x];
    stype[x] = 2;
    ds.insert({-location[x], x});
    vector<int> l, m, r;
    for (int i=1; i<N; i++){
        if (i == x) continue;
        dx[i] = getDistance(x, i);
        if (dx[i] < d0[x]) m.push_back(i);
        else if (d0[i] == d0[x]+dx[i]) l.push_back(i);
        else r.push_back(i);
    }
    cout << l.size() << " " << m.size() << " " << r.size() << endl;
    for (int i : m){
        location[i] = location[x]-dx[i];
        stype[i] = 1;
        cs.insert({location[i], i});
    }
    sort(l.begin(), l.end(), [](int a, int b){return d0[a] < d0[b];});
    for (int i : l){
        auto [yl, y] = *cs.begin();
        int dy = getDistance(y, i);
        int z = dx[i]-dx[y]-dy;
        z = -z;
        int pl = yl+z/2+dx[i]-(location[x]-(yl+z/2));
        if (cs.lower_bound({yl+z/2, -1})->first == yl+z/2){
            location[i] = pl;
            stype[i] = 2;
            ds.insert({-location[i], i});
        }
        else {
            location[i] = location[x]-dx[i];
            stype[i] = 1;
            cs.insert({location[i], i});
        }
    }
    sort(r.begin(), r.end(), [](int a, int b){return d0[a] < d0[b];});
    for (int i : r){
        auto [yl, y] = *ds.begin();
        yl = -yl;
        int dy = getDistance(y, i);
        int z = d0[i]-d0[y]-dy;
        z = -z;
        int pl = yl-z/2-(d0[i]-((yl-z/2)-location[0]));
        if (ds.lower_bound({-(yl-z/2), -1})->first == -(yl-z/2)){
            location[i] = pl;
            stype[i] = 1;
            cs.insert({location[i], i});
        }
        else {
            location[i] = location[0]+d0[i];
            stype[i] = 2;
            ds.insert({-location[i], i});
        }
    }
    /*for (int i=0; i<N; i++){
        cout << stype[i] << " " << location[i] << endl;
    }*/
}

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