Submission #1005905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005905		gyg	Rail (IOI14_rail)	C++17	56 / 100	44 ms	856 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e3 + 5, INF = 1e9;

int n;
int pos[MAX_N], type[MAX_N];
int dist0[MAX_N];
void init() {
    for (int i = 0; i < n; i++) {
        pos[i] = type[i] = -1;
        dist0[i] = 0;
    }
}

set<pii> ups; // Right of 0
set<pii> downs; // Left of 0
bool try_down(int i) {
    if (ups.empty()) return false;

    int f = ups.rbegin()->second;
    int dist = getDistance(i, f);
    int new_pos = pos[f] - dist;
    assert(ups.upper_bound({new_pos, INF}) != ups.end());
    int j = ups.upper_bound({new_pos, INF})->second;
    // cout << i << " " << j << endl;

    if (dist0[j] + getDistance(j, i) != dist0[i]) return false;
    type[i] = 1, pos[i] = new_pos;
    if (pos[i] < pos[0]) downs.insert({pos[i], i});
    return true;
}
bool try_up(int i) {
    if (downs.empty()) return false;

    int s = downs.begin()->second;
    int dist = getDistance(i, s);
    // cout << i << " " << s << endl;
    int new_pos = pos[s] + dist;
    if (downs.upper_bound({new_pos, INF}) == downs.begin()) return false;
    int j = next(downs.upper_bound({new_pos, INF}), -1)->second;

    if (dist0[j] + getDistance(j, i) != dist0[i]) return false;
    type[i] = 2, pos[i] = new_pos;
    return true;
}

void comp() {
    vector<pii> ord;
    for (int i = 1; i < n; i++) ord.push_back({dist0[i], i});
    sort(ord.begin(), ord.end());
        
    for (pii x : ord) {
        int i = x.second;
        // cout << dist0[i] << " " << i << endl;
        if (try_up(i)) continue;
        if (try_down(i)) continue;
        
        type[i] = 2, pos[i] = pos[0] + dist0[i];
        ups.insert({pos[i], i});
    }
}

void findLocation(int tmp_n, int tmp_pos0, int tmp_pos[], int tmp_type[]) {
    n = tmp_n;
    init();
    pos[0] = tmp_pos0, type[0] = 1;
    for (int i = 1; i < n; i++) dist0[i] = getDistance(0, i);

    comp();

    for (int i = 0; i < n; i++) {
        tmp_pos[i] = pos[i], tmp_type[i] = type[i];
    }
    
    for (int i = 0; i < n; i++) {
        // cout << i << ": " << dist0[i] << endl;
        // cout << i << ": " << type[i] << " " << pos[i] << endl;
    }

}

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