oj.uz

답안 #73291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73291 2018-08-28T06:48:08 Z funcsr 철로 (IOI14_rail) C++17
100 / 100
 206 ms 100296 KB 
#include "rail.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
using namespace std;
typedef pair<int, int> P;

int cache[5001][5001];
int query(int x, int y) {
  if (cache[x][y] != -1) return cache[x][y];
  if (x == y) return cache[x][y] = 0;
  return cache[x][y] = cache[y][x] = getDistance(x, y);
}
#define DOWN 1
#define UP 2

void findLocation(int N, int pos0, int location[], int stype[]) {
  if (N == 1) {
    location[0] = pos0;
    stype[0] = 1;
    return;
  }

  rep(i, N) rep(j, N) cache[i][j] = -1;
  rep(i, N) location[i] = stype[i] = -1;
  location[0] = pos0;
  stype[0] = DOWN;
  P mp = P(INF, -1);
  rep(i, N) if (i != 0) mp = min(mp, P(query(0, i), i));
  int a = mp._2, d = mp._1;
  location[a] = pos0 + d;
  stype[a] = UP;
  int posa = location[a];

  vector<P> left, right;

  rep(i, N) if (i != 0 && i != a) {
    int d0 = query(0, i), da = query(a, i);
    if (d0 < d) {
      // (E)
      stype[i] = DOWN;
      location[i] = location[a]-da;
      assert(pos0 < location[i] && location[i] < location[a]);
    }
    else {
      if (d0-da == d) {
        // (A) or (B)
        left.pb(P(da-d, i));
      }
      else {
        // (C) or (D)
        right.pb(P(d0, i));
      }
    }
  }

  sort(all(left));
  int l = -1;
  map<int, bool> up;
  for (P p : left) {
    int r = p._1, b = p._2;
    if (l == -1) {
      location[b] = pos0-r;
      up[location[b]] = true;
      stype[b] = DOWN;
      l = b;
    }
    else {
      int s = (query(b, l) + r - (pos0-location[l]))/2;
      if (up[pos0 - (r-s)]) {
        location[b] = pos0-(r-s)+s;
        stype[b] = UP;
      }
      else {
        location[b] = pos0-r;
        up[location[b]] = true;
        stype[b] = DOWN;
        l = b;
      }
    }
  }

  sort(all(right));
  l = -1;
  up.clear();
  for (P p : right) {
    int r = p._1, b = p._2;
    if (l == -1) {
      location[b] = pos0+r;
      up[location[b]] = true;
      stype[b] = UP;
      l = b;
    }
    else {
      int s = (query(b, l) + r - (location[l]-pos0))/2;
      if (up[pos0 + (r-s)]) {
        location[b] = pos0+(r-s)-s;
        stype[b] = DOWN;
      }
      else {
        location[b] = pos0+r;
        up[location[b]] = true;
        stype[b] = UP;
        l = b;
      }
    }
  }
  rep(i, N) assert(location[i] != -1 && stype[i] != -1);
  rep(i, N) assert(0 <= location[i] && location[i] < 1000000);
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:41:7: warning: unused variable 'posa' [-Wunused-variable]
   int posa = location[a];
       ^~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 2 ms 916 KB Output is correct
3 Correct 3 ms 924 KB Output is correct
4 Correct 4 ms 992 KB Output is correct
5 Correct 3 ms 992 KB Output is correct
6 Correct 3 ms 992 KB Output is correct
7 Correct 4 ms 1012 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 2 ms 1204 KB Output is correct
7 Correct 3 ms 1208 KB Output is correct
8 Correct 2 ms 1216 KB Output is correct
9 Correct 3 ms 1280 KB Output is correct
10 Correct 3 ms 1284 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 98976 KB Output is correct
2 Correct 174 ms 98976 KB Output is correct
3 Correct 199 ms 99132 KB Output is correct
4 Correct 175 ms 99132 KB Output is correct
5 Correct 181 ms 99156 KB Output is correct
6 Correct 176 ms 99188 KB Output is correct
7 Correct 178 ms 99228 KB Output is correct
8 Correct 165 ms 99284 KB Output is correct
9 Correct 192 ms 99316 KB Output is correct
10 Correct 206 ms 99360 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 99360 KB Output is correct
2 Correct 186 ms 99404 KB Output is correct
3 Correct 167 ms 99460 KB Output is correct
4 Correct 174 ms 99460 KB Output is correct
5 Correct 175 ms 99536 KB Output is correct
6 Correct 174 ms 99584 KB Output is correct
7 Correct 167 ms 99752 KB Output is correct
8 Correct 187 ms 99752 KB Output is correct
9 Correct 174 ms 99752 KB Output is correct
10 Correct 181 ms 99900 KB Output is correct
11 Correct 172 ms 99928 KB Output is correct
12 Correct 176 ms 100116 KB Output is correct
13 Correct 184 ms 100116 KB Output is correct
14 Correct 176 ms 100116 KB Output is correct
15 Correct 184 ms 100116 KB Output is correct
16 Correct 181 ms 100116 KB Output is correct
17 Correct 176 ms 100116 KB Output is correct
18 Correct 185 ms 100256 KB Output is correct
19 Correct 181 ms 100296 KB Output is correct
20 Correct 171 ms 100296 KB Output is correct