oj.uz

Submission #959652

# Submission time Handle Problem Language Result Execution time Memory
959652 2024-04-08T15:40:26 Z vjudge1 Rail (IOI14_rail) C++17
30 / 100
 241 ms 98560 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 5e3;

int n, dis[N][N];

void findLocation(int NN, int first, int location[], int stype[]) {
  n = NN;

  for (int i = 0; i < n; i++) {
    dis[i][i] = 0;
    for (int j = i+1; j < n; j++) {
      dis[i][j] = dis[j][i] = getDistance(i, j);
    }
  }

  int x = 1;
  int mn = dis[0][1];
  for (int i = 2; i < n; i++) {
    if (dis[0][i] < mn) {
      mn = dis[0][i];
      x = i;
    }
  }
  stype[0] = 1;
  location[0] = first;
  stype[x] = 2;
  location[x] = first + dis[0][x];

  vector<pair<int, int>> a;
  for (int i = 1; i < n; i++) {
    if (i == x) continue;
    a.push_back(make_pair(dis[0][i], i));
  }
  sort(all(a));
  
  vector<int> l, r;
  r.push_back(x);
  for (int i = 0; i < n-2; i++) {
    int d = a[i].first;
    int idx = a[i].second;

    bool found = 0;

    // es uno de tipo 2 a mi izquierda
    // cojo el primero hacia arriba y luego uno hacia abajo
    for (int& j : l) {
      if (d == dis[0][x] + dis[x][j] + dis[j][idx]) {
        stype[idx] = 2;
        location[idx] = location[j] + dis[j][idx];
        found = 1;
        break;
      }
    }
    if (found) continue;

    // es uno de tipo 1
    // cojo uno hacia arriba
    for (int& j : r) {
      if (d == dis[0][j] + dis[j][idx]) {
        stype[idx] = 1;
        location[idx] = location[j] - dis[j][idx];
        found = 1;
        break;
      }
    }
    if (found) continue;


    // es uno nuevo a la derecha
    stype[idx] = 2;
    location[idx] = first + dis[0][idx];
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2400 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 98560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 98396 KB Output isn't correct
2 Halted 0 ms 0 KB -