제출 #103275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103275		naoai	철로 (IOI14_rail)	C++14	30 / 100	82 ms	860 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int nmax = 5000;

static int v[nmax + 1];
static int tip[nmax + 1];

int d0[nmax + 1];
pair<int, int> ord[nmax + 1];

set<int> C, D;

bool checkC (int pos, int L, int ind, int dL) {
    set<int>::iterator it = D.upper_bound(max(v[0], pos));

    if (it == D.end())
        return 0;

    if (d0[ind] != *it * 2 - v[0] - pos)
        return 0;

    it = D.upper_bound(max(v[0], v[L]));
    if (it == D.end())
        return 0;
    return (dL == *it * 2 - v[L] - pos);
}

void findLocation(int N, int first, int location[], int stype[]) {
    v[0] = first;
    tip[0] = 1;

    for (int i = 1; i < N; ++ i) {
        int x;
        x = getDistance(0, i);
        d0[i] = x;

        ord[i] = {d0[i], i};
    }

    sort(ord + 1, ord + N);
    int l = 0, r = ord[1].second;
    v[r] = v[0] + d0[r];
    tip[r] = 2;

    C.insert(v[0]);
    D.insert(v[r]);

    for (int i = 2; i < N; ++ i) {
        int c = ord[i].second;
        //cout << "!" << c << "\n";

        int dl = getDistance(c, l), dr = getDistance(c, r);

        int x = v[r] - dr;
        if (checkC(x, l, c, dl)) {
            tip[c] = 1;
            v[c] = x;
            C.insert(v[c]);
        } else {
            tip[c] = 2;
            v[c] = v[l] + dl;
            D.insert(v[c]);
        }

        if (v[c] > v[r])
            r = c;
        if (v[c] < v[l])
            l = c;
    }

    for (int i = 0; i < N; ++ i) {
        location[i] = v[i];
        //cout << "!" << tip[i] << " " << v[i] << "\n";
        stype[i] = tip[i];
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44