oj.uz

Submission #102759

# Submission time Handle Problem Language Result Execution time Memory
102759 2019-03-27T12:17:01 Z wxh010910 Rail (IOI14_rail) C++17
100 / 100
 98 ms 760 KB 
#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

void findLocation(int N, int first, int location[], int stype[]) {
  location[0] = first;
  stype[0] = 1;
  vector<int> dist0(N);
  for (int i = 1; i < N; ++i) {
    dist0[i] = getDistance(0, i);
  }
  int p = 1;
  for (int i = 2; i < N; ++i) {
    if (dist0[p] > dist0[i]) {
      p = i;
    }
  }
  location[p] = first + dist0[p];
  stype[p] = 2;
  vector<int> distp(N);
  vector<int> left;
  vector<int> right;
  for (int i = 1; i < N; ++i) {
    if (i != p) {
      distp[i] = getDistance(p, i);
      if (dist0[i] == distp[i] + dist0[p] && distp[i] <= dist0[p]) {
        location[i] = location[p] - distp[i];
        stype[i] = 1;
      } else {
        if (dist0[i] == distp[i] + dist0[p]) {
          left.push_back(i);
        } else {
          right.push_back(i);
        }
      }
    }
  }
  {
    sort(left.begin(), left.end(), [&](int a, int b) {
      return distp[a] < distp[b];
    });
    vector<int> down;
    down.push_back(0);
    for (auto i : left) {
      int foo = location[p] - distp[i];
      int bar = location[down.back()] + getDistance(down.back(), i);
      int near = -1;
      for (auto j : down) {
        if (location[j] <= bar) {
          near = j;
          break;
        }
      }
      if (location[near] - foo == bar - location[near]) {
        location[i] = bar;
        stype[i] = 2;
      } else {
        location[i] = foo;
        stype[i] = 1;
        down.push_back(i);
      }
    }
  }
  {
    sort(right.begin(), right.end(), [&](int a, int b) {
      return dist0[a] < dist0[b];
    });
    vector<int> up;
    up.push_back(p);
    for (auto i : right) {
      int foo = location[0] + dist0[i];
      int bar = location[up.back()] - getDistance(up.back(), i);
      int near = -1;
      for (auto j : up) {
        if (location[j] >= bar) {
          near = j;
          break;
        }
      }
      if (foo - location[near] == location[near] - bar) {
        location[i] = bar;
        stype[i] = 1;
      } else {
        location[i] = foo;
        stype[i] = 2;
        up.push_back(i);
      }
    }
  }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 504 KB Output is correct
2 Correct 78 ms 608 KB Output is correct
3 Correct 75 ms 632 KB Output is correct
4 Correct 79 ms 604 KB Output is correct
5 Correct 79 ms 676 KB Output is correct
6 Correct 80 ms 632 KB Output is correct
7 Correct 73 ms 604 KB Output is correct
8 Correct 98 ms 632 KB Output is correct
9 Correct 73 ms 628 KB Output is correct
10 Correct 81 ms 632 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 620 KB Output is correct
2 Correct 77 ms 604 KB Output is correct
3 Correct 80 ms 636 KB Output is correct
4 Correct 79 ms 632 KB Output is correct
5 Correct 82 ms 548 KB Output is correct
6 Correct 76 ms 628 KB Output is correct
7 Correct 76 ms 612 KB Output is correct
8 Correct 74 ms 632 KB Output is correct
9 Correct 74 ms 632 KB Output is correct
10 Correct 74 ms 760 KB Output is correct
11 Correct 76 ms 632 KB Output is correct
12 Correct 74 ms 632 KB Output is correct
13 Correct 81 ms 632 KB Output is correct
14 Correct 80 ms 632 KB Output is correct
15 Correct 87 ms 760 KB Output is correct
16 Correct 84 ms 632 KB Output is correct
17 Correct 78 ms 732 KB Output is correct
18 Correct 76 ms 632 KB Output is correct
19 Correct 81 ms 632 KB Output is correct
20 Correct 86 ms 632 KB Output is correct