oj.uz

Submission #959653

# Submission time Handle Problem Language Result Execution time Memory
959653 2024-04-08T15:41:59 Z vjudge1 Rail (IOI14_rail) C++17
56 / 100
 391 ms 98772 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];
        l.push_back(idx);
        found = 1;
        break;
      }
    }
    if (found) continue;


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

Subtask #1
8.0 / 8.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 #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 2648 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 98308 KB Output is correct
2 Correct 323 ms 98396 KB Output is correct
3 Correct 330 ms 98564 KB Output is correct
4 Correct 314 ms 98588 KB Output is correct
5 Correct 363 ms 98480 KB Output is correct
6 Correct 360 ms 98444 KB Output is correct
7 Correct 366 ms 98772 KB Output is correct
8 Correct 311 ms 98376 KB Output is correct
9 Correct 337 ms 98608 KB Output is correct
10 Correct 344 ms 98588 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 98640 KB Output is correct
2 Correct 314 ms 98388 KB Output is correct
3 Correct 328 ms 98588 KB Output is correct
4 Correct 310 ms 98420 KB Output is correct
5 Correct 371 ms 98580 KB Output is correct
6 Correct 391 ms 98580 KB Output is correct
7 Correct 365 ms 98584 KB Output is correct
8 Correct 324 ms 98440 KB Output is correct
9 Correct 345 ms 98440 KB Output is correct
10 Correct 338 ms 98424 KB Output is correct
11 Incorrect 366 ms 98588 KB Output isn't correct
12 Halted 0 ms 0 KB -