제출 #1146861

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

rail

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

#define ll long long
void findLocation(int n, int first, int location[], int stype[]){
    unordered_map<int,int> loc;
    unordered_map<int,int>type;
    loc[0] = first;
    type[0] = 1;
    vector<int> dis_0(n);
    vector<pair<int,int>>order;
    for(int i=1;i<n;i++){
        dis_0[i] = getDistance(i,0);
        order.emplace_back(dis_0[i], i);
    }
    sort(order.begin(), order.end());
    int x = order[0].second;
    loc[x] = first + order[0].first;
    type[x] = 2;
    
    vector<int>dis_x;
    dis_x[0] = dis_0[x];
    vector<pair<int,int>> L, R;
    //procesa los demas
    for(int i=1;i<n-1;i++){
        auto [_,y] = order[i];
        dis_x[y] = getDistance(x,y);
       
        if(dis_0[y] == dis_0[x] + dis_x[y]){ //izq x
            if(dis_x[y] < dis_x[0]){ //entre 0 y x
                loc[y] = loc[x] - dis_x[y];
                type[y] = 1;
            }else{ //izq 0
                L.emplace_back(dis_x[y], y);
            }
        }else{ //der equis
            R.emplace_back(dis_0[y], y);
        }
    }
    unordered_map<int,int> seen;
    sort(R.begin(), R.end());
    int r =  x; //temp del mas derecho
    for(auto[_, y] : R){
        int loc_y = loc[r] - getDistance(r, y);
        int loc_z  = (loc[0] + loc_y + dis_0[y]) / 2; //
        if(seen.count(loc_z) && type[seen[loc_z]] == 2){
            loc[y] = loc_y;
            type[y] = 1;
        }else{
            loc[y] = loc[0] + dis_0[y];
            type[y] = 2,
            r = y;
        }
        seen[loc[y]] = y;
    }
    sort(L.begin(), L.end());
    int l = 0; //temp del mas izquierda
    for(auto[_, y] : L){
         int loc_y = loc[l] + getDistance(l, y);
         int loc_z  = (loc[x] + loc_y - getDistance(x, y)) / 2; //
        if(seen.count(loc_z) && type[seen[loc_z]] == 1){
            loc[y] = loc_y;
            type[y] = 2;
        }else{
            loc[y] = loc[x] - dis_x[y];
            type[y] = 1,
            l = y;
        }
        seen[loc[y]] = y;
    }
    for(auto[i, loc_i]: loc){
        location[i] = loc_i;
        stype[i] = type[i];
    }
}

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