oj.uz

Submission #556042

# Submission time Handle Problem Language Result Execution time Memory
556042 2022-05-02T08:47:48 Z MilosMilutinovic Rail (IOI14_rail) C++14
100 / 100
 101 ms 32128 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 5005;

int dist[MAX][MAX];

int ask(int i, int j) {
  if (i == j) {
    return 0;
  }
  if (i > j) {
    swap(i, j);
  }
  if (!dist[i][j]) {
    dist[i][j] = getDistance(i, j);
  }
  return dist[i][j];
}

void findLocation(int n, int first, int location[], int stype[]) {
  map<int, int> mp;
  location[0] = first;
  stype[0] = 1;
  mp[location[0]] = 1;
  if (n == 1) {
    return;
  }
  vector<int> d0(n);
  for (int i = 1; i < n; i++) {
    d0[i] = ask(0, i);
  }
  int idx = 1;
  for (int i = 2; i < n; i++) {
    if (d0[i] < d0[idx]) {
      idx = i;
    }
  }
  location[idx] = first + d0[idx];
  stype[idx] = 2;
  mp[location[idx]] = 2;
  vector<int> dx(n);
  for (int i = 0; i < n; i++) {
    dx[i] = ask(idx, i);
  }
  vector<int> l;
  vector<int> r;
  for (int i = 1; i < n; i++) {
    if (i == idx) {
      continue;
    }
    if (d0[i] == ask(0, idx) + dx[i]) {
      if (d0[idx] > dx[i]) {
        location[i] = location[idx] - dx[i];
        stype[i] = 1;
        mp[location[i]] = 1;
      } else {
        l.push_back(i);
      }
    } else {
      r.push_back(i);
    }
  }
  sort(l.begin(), l.end(), [&](int i, int j) {
    return dx[i] < dx[j];
  });
  sort(r.begin(), r.end(), [&](int i, int j) {
    return d0[i] < d0[j];
  });
  int R = idx;
  for (int id = 0; id < r.size(); id++) {
    int i = r[id];
    int d = (d0[R] + ask(R, i) - ask(0, i)) / 2;
    if (mp[location[R] - d] == 2) {
      location[i] = location[R] - ask(R, i);
      stype[i] = 1;
      mp[location[i]] = 1;
    } else {
      location[i] = location[0] + ask(0, i);
      stype[i] = 2;
      mp[location[i]] = 2;
      R = i;
    }
  }
  int L = 0;
  for (int id = 0; id < l.size(); id++) {
    int i = l[id];
    int d = (dx[L] + ask(L, i) - ask(idx, i)) / 2;
    if (mp[location[L] + d] == 1) {
      location[i] = location[L] + ask(L, i);
      stype[i] = 2;
      mp[location[i]] = 2;
    } else {
      location[i] = location[idx] - ask(idx, i);
      stype[i] = 1;
      mp[location[i]] = 1;
      L = i;
    }
  }
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int id = 0; id < r.size(); id++) {
      |                    ~~~^~~~~~~~~~
rail.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int id = 0; id < l.size(); id++) {
      |                    ~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 20232 KB Output is correct
2 Correct 91 ms 18952 KB Output is correct
3 Correct 82 ms 22528 KB Output is correct
4 Correct 81 ms 20980 KB Output is correct
5 Correct 82 ms 22268 KB Output is correct
6 Correct 86 ms 24316 KB Output is correct
7 Correct 91 ms 28548 KB Output is correct
8 Correct 87 ms 30464 KB Output is correct
9 Correct 86 ms 19452 KB Output is correct
10 Correct 89 ms 32128 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 20172 KB Output is correct
2 Correct 101 ms 18932 KB Output is correct
3 Correct 97 ms 22532 KB Output is correct
4 Correct 83 ms 21000 KB Output is correct
5 Correct 81 ms 22264 KB Output is correct
6 Correct 84 ms 24324 KB Output is correct
7 Correct 88 ms 28628 KB Output is correct
8 Correct 86 ms 30456 KB Output is correct
9 Correct 99 ms 19572 KB Output is correct
10 Correct 92 ms 32076 KB Output is correct
11 Correct 87 ms 29580 KB Output is correct
12 Correct 86 ms 20428 KB Output is correct
13 Correct 86 ms 26872 KB Output is correct
14 Correct 89 ms 23172 KB Output is correct
15 Correct 86 ms 25988 KB Output is correct
16 Correct 84 ms 24180 KB Output is correct
17 Correct 82 ms 23300 KB Output is correct
18 Correct 90 ms 28412 KB Output is correct
19 Correct 92 ms 27640 KB Output is correct
20 Correct 79 ms 18820 KB Output is correct