Submission #417829

#	Time	Username	Problem	Language	Result	Execution time	Memory
417829		qwerasdfzxcl	Rail (IOI14_rail)	C++14	30 / 100	223 ms	560 KiB

rail

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

using namespace std;
typedef long long ll;
bool chk[5050];
int n;

bool valid(int v, int x, int* location, int* stype){
    if (location[0]<=v) return (v-location[0]==x);
    int x1=-1e9, x2=1e9;
    for (int i=0;i<n;i++) if (chk[i]){
        if (location[i]>location[0] && location[i]<x2 && stype[i]==2) x2 = location[i];
    }
    for (int i=0;i<n;i++) if (chk[i]){
        if (location[i]<v && location[i]>x1 && stype[i]==1) x1 = location[i];
    }
    return (x2+(x2-x1)+(v-x1))==x;
}

bool valid2(int v, int r, int x, int* location, int* stype){
    if (v<=location[r]){
        int x2 = -1e9;
        for (int i=0;i<n;i++) if (chk[i]){
            if (location[i]<v && location[i]>x2 && stype[i]==1) x2 = location[i];
        }
        return location[r]-x2+(v-x2)==x;
    }
    int x1=-1e9;
    for (int i=0;i<n;i++) if (chk[i]){
        if (location[i]<location[r] && location[i]>x1 && stype[i]==1) x1 = location[i];
    }
    return location[r]-x1+(v-x1)==x;
}

void debug(int* location, int* stype){
    for (int i=0;i<n;i++){
        if (!chk[i]) printf("X ");
        else printf("%d ", location[i]);
    }
    printf("\n");
    for (int i=0;i<n;i++){
        if (!chk[i]) printf("X ");
        else printf("%d ", stype[i]);
    }
    printf("\n\n");
}

void findLocation(int N, int first, int location[], int stype[]){
    n = N;
    vector<pair<int, int>> d;
    for (int i=1;i<=N-1;i++) d.emplace_back(getDistance(0, i), i);
    sort(d.begin(), d.end());
    location[0] = first;
    stype[0] = 1;
    location[d[0].second] = first+d[0].first;
    stype[d[0].second] = 2;
    chk[0] = 1, chk[d[0].second] = 1;
    //debug(location, stype);
    int L = 0, R = d[0].second;
    for (int z=1;z<N-1;z++){
        int cur = d[z].second, val = d[z].first;
        int LD = getDistance(L, cur), RD = getDistance(R, cur);
        if (valid(location[L]+LD, val, location, stype) && valid2(location[L]+LD, R, RD, location, stype)){
            location[cur] = location[L]+LD, stype[cur] = 2;
            if (location[cur]>location[R]) R = cur;
        }
        else{
            location[cur] = location[R]-RD, stype[cur] = 1;
            if (location[cur]<location[L]) L = cur;
        }
        chk[cur] = 1;
        //debug(location, stype);
    }
}

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