제출 #1160813

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

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int n, int first, int location[], int stype[]){
    map<pair<int, int>, int>cache;
    auto get = [&] (int i, int j){
        if(i == j){
            return 0;
        }
        if(i > j){
            swap(i, j);
        }
        auto it = cache.find(make_pair(i, j));
        if(it != cache.end()){
            return it->second;
        }
        return cache[make_pair(i, j)] = getDistance(i, j);
    };
    location[0] = first;
    int d = stype[0] = 1;
    for(int i = 2; i < n; i++){
        if(get(0, i) < get(0, d)){
            d = i;
        }
    }
    if(n == 1){
        return;
    }
    stype[d] = 2;
    location[d] = first + get(0, d);
    vector<int>left, right;
    for(int i = 1; i < n; i++){
        if(i != d && get(0, i) - get(d, i) == get(0, d)){
            left.emplace_back(i);
        }
        else if(i != d){
            right.emplace_back(i);
        }
    }
    if(!left.empty()){
        sort(left.begin(), left.end(), [&] (int i, int j){
            return get(d, i) < get(d, j);
        });
        stype[left[0]] = 1;
        location[left[0]] = location[d] - get(d, left[0]);
        for(int i = 1, p = 0; i < left.size(); i++){
            if(get(left[p], left[i]) == get(d, left[i]) - get(d, left[p])){
                stype[left[i]] = 2;
                location[left[i]] = location[left[p]] + get(left[p], left[i]);
            }
            else{
                stype[left[p = i]] = 1;
                location[left[i]] = location[d] - get(d, left[i]);
            }
        }
    }
    if(!right.empty()){
        sort(right.begin(), right.end(), [&] (int i, int j){
            return get(d, i) < get(d, j);
        });
        stype[right[0]] = 2;
        location[right[0]] = first + get(0, right[0]);
        for(int i = 1, p = 0; i < right.size(); i++){
            if(get(right[p], right[i]) == get(d, right[i]) - get(d, right[p])){
                stype[right[i]] = 1;
                location[right[i]] = location[right[p]] - get(right[p], right[i]);
            }
            else{
                stype[right[p = i]] = 2;
                location[right[i]] = first + get(0, right[i]);
            }
        }
    }
}

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