제출 #581449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581449		wdjpng	철로 (IOI14_rail)	C++17	30 / 100	387 ms	196388 KiB

rail

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

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

void findLocation(signed n, signed first, signed location[], signed stype[])
{
    vector<vector<int>>dist(n, vector<int>(n));
    rep(i,n) rep(j,i) dist[i][j]=getDistance(i,j);
    rep(i,n) for(int j = i+1; j < n; j++) dist[i][j]=dist[j][i];

    int minn=1e12,mini=-1;
    for(int i = 1; i < n; i++) if(dist[0][i]<minn) {minn=dist[0][i]; mini=i;}

    stype[0]=1;
    stype[mini]=2;
    location[0]=first;
    location[mini]=first+dist[0][mini];

    rep(i,n) {
        if(i==0||i==mini) continue;
        if(dist[i][mini]+dist[mini][0] == dist[i][0]) // on the left 
        {
            stype[i]=1;
            location[i]=location[mini]-dist[i][mini];
        } else {
            stype[i]=2;
            location[i]=location[0]+dist[0][i];
        }
    }
}

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