Submission #365307

#	Time	Username	Problem	Language	Result	Execution time	Memory
365307		79brue	Rail (IOI14_rail)	C++14	30 / 100	98 ms	4588 KiB

rail

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

using namespace std;

int n, s, c;
int a[5002];
int b[5002];
vector<pair<int, int> > vec1, vec2;

int type[3000002];

void findLocation(int N, int first, int location[], int stype[]){
    if(N==1){
        location[0] = first;
        stype[0] = 1;
        return;
    }
    n = N, s = first;
    for(int i=1; i<n; i++) a[i] = getDistance(0, i);
    c = min_element(a+1, a+n) - a;
    for(int i=0; i<n; i++){
        if(i!=c){
            b[i] = getDistance(c, i);
        }
    }

    location[0] = s;
    stype[0] = 1;
    type[s] = 1;
    location[c] = a[c] + s;
    stype[c] = 2;
    type[location[c]] = 2;

    for(int i=1; i<n; i++){
        if(i==c) continue;
        if(b[i] < b[0]){
            location[i] = location[c] - b[i];
            stype[i] = 1;
            type[location[i]] = 1;
            continue;
        }
        if(a[i] == a[c] + b[i]) vec2.push_back(make_pair(b[i], i));
        else vec1.push_back(make_pair(a[i], i));
    }

    sort(vec1.begin(), vec1.end());
    sort(vec2.begin(), vec2.end());

    int r = 0;
    int rLoc = 0;
    for(auto p: vec1){
        int x = p.second, dist = p.first;
        if(!r){
            location[x] = s + dist;
            stype[x] = 2;
            r = x;
            rLoc = s+dist;
            type[location[x]] = 2;
            continue;
        }

        int tmp = getDistance(r, x);
        int tmp2 = a[r] + tmp - a[x];
//        assert(tmp2 >= 0 && type[rLoc - tmp2/2]);
        if(type[rLoc - tmp2/2] == 2){
            location[x] = rLoc - tmp;
            stype[x] = 1;
            type[location[x]] = 1;
        }
        else{
            location[x] = s + dist;
            stype[x] = 2;
            r = x;
            rLoc = s + dist;
            type[location[x]] = 2;
        }
    }

    s = location[c];

    r = 0;
    rLoc = 0;
    for(auto p: vec2){
        int x = p.second, dist = p.first;
        if(!r){
            location[x] = s - dist;
            stype[x] = 1;
            r = x;
            rLoc = s-dist;
            type[location[x]] = 1;
            continue;
        }

        int tmp = getDistance(r, x);
        int tmp2 = b[r] + tmp - b[x];
        if(type[rLoc + tmp2/2] == 1){
            location[x] = rLoc + tmp;
            stype[x] = 2;
            type[location[x]] = 2;
        }
        else{
            location[x] = s - dist;
            stype[x] = 1;
            r = x;
            rLoc = s - dist;
            type[location[x]] = 1;
        }
    }
}

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