oj.uz

답안 #168657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168657 2019-12-14T20:19:12 Z dolphingarlic 철로 (IOI14_rail) C++14
100 / 100
 88 ms 4544 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

int A = 0, B, C, D;
int from_A[5001], from_B[5001], visited[1000001];

bool left_cmp(int X, int Y) { return from_B[X] < from_B[Y]; }
bool right_cmp(int X, int Y) { return from_A[X] < from_A[Y]; }

void findLocation(int N, int first, int location[], int stype[]) {
    location[A] = first;
    visited[location[A]] = stype[A] = 1;

    int min_from_A = INT_MAX;
    for (int i = 1; i < N; i++) {
        from_A[i] = getDistance(A, i);
        if (from_A[i] < min_from_A) {
            min_from_A = from_A[i];
            B = i;
        }
    }

    location[B] = first + from_A[B];
    visited[location[B]] = stype[B] = 2;

    vector<int> left, right;

    for (int i = 1; i < N; i++) {
        if (i == B) continue;
        from_B[i] = getDistance(B, i);
        if (from_B[i] < from_A[B] && i != 2222) {
            location[i] = location[B] - from_B[i];
            visited[location[i]] = stype[i] = 1;
        } else if (from_A[B] + from_B[i] == from_A[i]) left.push_back(i);
        else right.push_back(i);
    }

    sort(left.begin(), left.end(), left_cmp);
    sort(right.begin(), right.end(), right_cmp);

    C = A;
    for (int i : left) {
        int from_C = getDistance(C, i);
        int z = from_B[i] - from_C - from_B[C];

        if (visited[location[C] - z / 2] == 1) {
            location[i] = location[C] + from_C;
            stype[i] = 2;
        } else {
            location[i] = location[B] - from_B[i];
            stype[i] = 1;
            C = i;
        }

        visited[location[i]] = stype[i];
    }

    D = B;
    for (int i : right) {
        int from_D = getDistance(D, i);
        int z = from_A[i] - from_D - from_A[D];

        if (visited[location[D] + z / 2] == 2) {
            location[i] = location[D] - from_D;
            stype[i] = 1;
        } else {
            location[i] = location[A] + from_A[i];
            stype[i] = 2;
            D = i;
        }

        visited[location[i]] = stype[i];
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 4088 KB Output is correct
2 Correct 86 ms 4176 KB Output is correct
3 Correct 86 ms 4344 KB Output is correct
4 Correct 86 ms 4344 KB Output is correct
5 Correct 86 ms 4324 KB Output is correct
6 Correct 88 ms 4216 KB Output is correct
7 Correct 86 ms 4216 KB Output is correct
8 Correct 85 ms 4344 KB Output is correct
9 Correct 86 ms 4224 KB Output is correct
10 Correct 87 ms 4344 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 4088 KB Output is correct
2 Correct 86 ms 4216 KB Output is correct
3 Correct 85 ms 4344 KB Output is correct
4 Correct 85 ms 4344 KB Output is correct
5 Correct 85 ms 4312 KB Output is correct
6 Correct 86 ms 4216 KB Output is correct
7 Correct 87 ms 4180 KB Output is correct
8 Correct 85 ms 4344 KB Output is correct
9 Correct 85 ms 4216 KB Output is correct
10 Correct 87 ms 4344 KB Output is correct
11 Correct 85 ms 4216 KB Output is correct
12 Correct 86 ms 4544 KB Output is correct
13 Correct 85 ms 4260 KB Output is correct
14 Correct 86 ms 4216 KB Output is correct
15 Correct 85 ms 4348 KB Output is correct
16 Correct 88 ms 4344 KB Output is correct
17 Correct 85 ms 4344 KB Output is correct
18 Correct 85 ms 4216 KB Output is correct
19 Correct 85 ms 4344 KB Output is correct
20 Correct 86 ms 4472 KB Output is correct