Submission #873505

#	Time	Username	Problem	Language	Result	Execution time	Memory
873505		velislavgarkov	Rail (IOI14_rail)	C++14	100 / 100	56 ms	4996 KiB

rail

#include "rail.h"
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
    int d;
    int ind;
};
Stantia st[MAXN];
int dist[2][MAXN];
int um[MAXM];
bool cmp(Stantia a, Stantia b) {
    return a.d<b.d;
}
void findLocation (int n, int first, int location[], int stype[]) {
    location[0]=first; stype[0]=1;
    memset(um,-1,sizeof(um));
    for (int i=1;i<n;i++) {
        st[i].d=dist[0][i]=getDistance(0,i);
        st[i].ind=i;
    }
    sort(st+1,st+n,cmp);
    location[st[1].ind]=first+st[1].d;
    stype[st[1].ind]=2;
    int mini=0, maxi=st[1].ind;
    um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;
    for (int i=0;i<n;i++) {
        if (i==st[1].ind) continue;
        dist[1][i]=getDistance(st[1].ind,i);
    }

    int l1, d1;
    for (int i=2;i<n;i++) {
        int cur=st[i].ind;
        if (dist[1][cur]+st[1].d!=st[i].d) {
            d1=getDistance(maxi,cur);
            l1=(dist[0][maxi]+d1-dist[0][cur])/2;
            l1=location[maxi]-l1;
            if (um[l1]!=-1 && stype[um[l1]]==2) {
                location[cur]=location[maxi]-d1;
                stype[cur]=1;
            } else {
                location[cur]=location[0]+dist[0][cur];
                stype[cur]=2;
                maxi=cur;
            }
            ///cout << "up " << st[i].ind << ' ' << location[st[i].ind] << endl;
            um[location[st[i].ind]]=st[i].ind;
        }
    }

    for (int i=2;i<n;i++) st[i].d=dist[1][st[i].ind];
    sort(st+2,st+n,cmp);
    for (int i=2;i<n;i++) {
        int cur=st[i].ind;
        if (dist[1][cur]+st[1].d==dist[0][cur]) {
            d1=getDistance(mini,cur);
            l1=(dist[1][mini]+d1-dist[1][cur])/2;
            l1=location[mini]+l1;
            if (um[l1]!=-1 && stype[um[l1]]==1) {
                location[cur]=location[mini]+d1;
                stype[cur]=2;
            } else {
                location[cur]=location[st[1].ind]-dist[1][cur];
                stype[cur]=1;
                mini=cur;
            }
            ///cout << cur << ' ' << location[cur] << endl;
            um[location[st[i].ind]]=st[i].ind;
        }
    }
}

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