oj.uz

Submission #39662

# Submission time Handle Problem Language Result Execution time Memory
39662 2018-01-17T03:21:03 Z funcsr Rail (IOI14_rail) C++14
56 / 100
 818 ms 98796 KB 
#include "rail.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<19)
#define INF 1145141919
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second

int memo[5000][5000];
int query(int a, int b) {
  if (memo[a][b] != -1) return memo[a][b];
  return memo[a][b] = getDistance(a, b);
}
void findLocation(int N, int first, int location[], int stype[]) {
  rep(i, N) rep(j, N) memo[i][j] = -1;
  rep(i, N) memo[i][i] = 0;
  P m = P(INF, -1);
  rep(i, N) if (i != 0) m = min(m, P(query(0, i), i));
  int a = m._2;
  m = P(INF, -1);
  rep(i, N) if (i != a) m = min(m, P(query(a, i), i));
  int b = m._2;
  location[0] = first;
  location[a] = location[0] + query(0, a);
  location[b] = location[a] - query(a, b);
  stype[a] = 2;
  stype[b] = 1;
  vector<P> ps;
  rep(i, N) if (i != a && i != b) ps.pb(P(query(a, i), i));
  sort(all(ps));
  vector<int> ls, rs;
  for (P pp : ps) {
    int i = pp._2, k = -1;
    if (query(a, i) < query(b, i)) {
      // left
      for (int p : ls) {
        if (query(p, i) + query(a, p) == query(a, i)) {
          k = p;
          break;
        }
      }
      if (k == -1) {
        stype[i] = 1;
        location[i] = location[a] - pp._1;
        ls.pb(i);
      }
      else {
        stype[i] = 2;
        location[i] = location[a] - (pp._1 - query(k, i)*2);
      }
    }
    else {
      // right
      for (int p : rs) {
        if (query(b, p) + query(p, i) == query(b, i)) {
          k = p;
          break;
        }
      }
      if (k == -1) {
        stype[i] = 2;
        location[i] = location[b] + pp._1 - query(a, b);
        rs.pb(i);
      }
      else {
        stype[i] = 1;
        location[i] = location[b] + (pp._1 - query(a, b) - query(k, i)*2);
      }
    }
  }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 98708 KB Output is correct
2 Correct 487 ms 98708 KB Output is correct
3 Correct 435 ms 98712 KB Output is correct
4 Correct 427 ms 98728 KB Output is correct
5 Correct 537 ms 98728 KB Output is correct
6 Correct 818 ms 98728 KB Output is correct
7 Correct 699 ms 98728 KB Output is correct
8 Correct 374 ms 98796 KB Output is correct
9 Correct 400 ms 98796 KB Output is correct
10 Correct 385 ms 98796 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 98796 KB Output is correct
2 Correct 402 ms 98796 KB Output is correct
3 Correct 382 ms 98796 KB Output is correct
4 Correct 360 ms 98796 KB Output is correct
5 Correct 491 ms 98796 KB Output is correct
6 Correct 588 ms 98796 KB Output is correct
7 Correct 426 ms 98796 KB Output is correct
8 Correct 374 ms 98796 KB Output is correct
9 Correct 380 ms 98796 KB Output is correct
10 Correct 376 ms 98796 KB Output is correct
11 Incorrect 475 ms 98796 KB Output isn't correct
12 Halted 0 ms 0 KB -