Submission #1281235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281235		repmann	철로 (IOI14_rail)	C++20	30 / 100	55 ms	57688 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int N;
int DIST[5000][5000];
//int getDistance(int i, int j)
//{
//  cout << i << ' ' << j << '\n';
//  int ret;
//  cin >> ret;
//  return ret;
//}
void findLocation(int n, int location0, int location[], int stype[])
{
  N = n;
  stype[0] = 1;
  location[0] = location0;
  vector <pair <int, int>> V, L, R;
  for(int i = 1; i < N; i++)
  {
    DIST[0][i] = DIST[i][0] = getDistance(0, i);
    V.push_back({DIST[0][i], i});
  }
  sort(V.begin(), V.end());
  int d = V.begin()->second;
  stype[d] = 2;
  location[d] = location[0] + V.begin()->first;
  for(int i = 1; i < N; i++)
  {
    if(i == d) continue;
    DIST[d][i] = DIST[i][d] = getDistance(d, i);
  }
  for(int i = 1; i < N; i++)
  {
    if(i == d) continue;
    if(DIST[0][i] == (DIST[0][d] + DIST[d][i])) L.push_back({DIST[d][i], i});
    else R.push_back({DIST[0][i], i});
  }
  if(L.size())
  {
    sort(L.begin(), L.end());
    while(L.begin()->first < DIST[d][0])
    {
      stype[L.begin()->second] = 1;
      location[L.begin()->second] = location[d] - L.begin()->first;
      L.erase(L.begin(), L.begin() + 1);
    }
    int cntd = 1, prevd = L.back().second;
    stype[prevd] = 2;
    location[prevd] = location[d] - DIST[d][prevd];
    for(int i = L.size() - 2; i >= 0; i--)
    {
      DIST[L[i].second][prevd] = DIST[prevd][L[i].second] = getDistance(L[i].second, prevd);
      if(DIST[d][prevd] == (L[i].first + DIST[L[i].second][prevd]))
      {
        stype[L[i].second] = 1;
        location[L[i].second] = location[d] - L[i].first;
      }
      else
      {
        cntd++;
        prevd = L[i].second;
        stype[prevd] = 2;
        location[prevd] = location[d] - DIST[d][prevd];
      }
    }
    if(cntd == L.size())
    {
      for(pair <int, int> p : L)
      {
        stype[p.second] = 1;
        location[p.second] = location[d] - p.first;
      }
    }
  }
  if(R.size())
  {
    sort(R.begin(), R.end());
    int cntc = 1, prevc = R.back().second;
    stype[prevc] = 1;
    location[prevc] = location[0] + DIST[0][prevc];
    for(int i = R.size() - 2; i >= 0; i--)
    {
      DIST[R[i].second][prevc] = DIST[prevc][R[i].second] = getDistance(R[i].second, prevc);
      if(DIST[0][prevc] == (R[i].first + DIST[R[i].second][prevc]))
      {
        stype[R[i].second] = 2;
        location[R[i].second] = location[0] + R[i].first;
      }
      else
      {
        cntc++;
        prevc = R[i].second;
        stype[prevc] = 1;
        location[prevc] = location[0] + DIST[0][prevc];
      }
    }
    if(cntc == R.size())
    {
      for(pair <int, int> p : R)
      {
        stype[p.second] = 2;
        location[p.second] = location[0] + p.first;
      }
    }
  }
  return;
}
//int main()
//{
//  int n, location0;
//  cin >> n >> location0;
//  int location[n], stype[n];
//  findLocation(n, location0, location, stype);
//  for(int i = 0; i < n; i++) cout << location[i] << " \n"[i == (n - 1)];
//  for(int i = 0; i < n; i++) cout << stype[i] << " \n"[i == (n - 1)];
//  return 0;
//}

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