Submission #872778

#	Time	Username	Problem	Language	Result	Execution time	Memory
872778		velislavgarkov	Rail (IOI14_rail)	C++17	30 / 100	70 ms	720 KiB

rail

#include "rail.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=1e5+10;
struct Stantia {
    int d1, d2, d3;
    int ind;
};
Stantia st[MAXN];
bool used[MAXN];
bool cmp(Stantia a, Stantia b) {
    return a.d1<b.d1;
}
void findLocation (int n, int first, int location[], int stype[]) {
    location[0]=first; stype[0]=1;
    used[0]=true;
    int minind=-1;
    for (int i=1;i<n;i++) {
        st[i].d1=getDistance(0,i);
        if (minind==-1 || st[minind].d1>st[i].d1) minind=i;
    }
    int maxind=0, maxd=0, d;
    st[0].d1=0;
    for (int i=1;i<n;i++) {
        if (i==minind) continue;
        d=getDistance(i,0);
        if (d+2*st[minind].d1==st[i].d1 && st[i].d1>st[maxind].d1) {
            maxind=i;
            maxd=d;
        }
    }
    used[maxind]=true;
    location[maxind]=first-maxd;
    stype[maxind]=1;

    int br=0;
    for (int i=1;i<n;i++) {
        if (i==maxind) continue;
        st[br].d1=getDistance(maxind,i);
        st[br].ind=i;
        br++;
    }
    sort(st,st+br,cmp);
    for (int i=0;i<br;i++) {
        if (used[st[i].ind]) continue;
        used[st[i].ind]=true;
        location[st[i].ind]=location[maxind]+st[i].d1;
        stype[st[i].ind]=2;
        for (int j=i+1;j<br;j++) {
            d=getDistance(st[i].ind,st[j].ind);
            if (st[i].d1+d==st[j].d1) {
                used[st[j].ind]=true;
                location[st[j].ind]=location[st[i].ind]-d;
                stype[st[j].ind]=1;
            }
        }
    }
}

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