Submission #872825

#	Time	Username	Problem	Language	Result	Execution time	Memory
872825		velislavgarkov	Rail (IOI14_rail)	C++14	30 / 100	48 ms	4708 KiB

rail

#include "rail.h"
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
    int d;
    int ind;
};
Stantia st[MAXN];
int dist[MAXN];
int um[MAXM];
set <int> lef, ri;
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;
    for (int i=1;i<n;i++) {
        st[i].d=dist[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;
    ri.insert(location[st[1].ind]);
    um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;

    int l1, d1, d2, cur_c, cur_ind;
    for (int i=2;i<n;i++) {
        d1=getDistance(st[i].ind,st[1].ind);
        if (d1+st[1].d==st[i].d && st[i].d>2*st[1].d) {
            if (mini==0) {
                location[st[i].ind]=location[st[1].ind]-(st[i].d-st[1].d);
                stype[st[i].ind]=1;
                lef.insert(-location[st[i].ind]);
                mini=st[i].ind;
            } else {
                l1=location[mini]+(st[i].d-dist[mini]);
                cur_c=-(*lef.lower_bound(-l1));
                cur_ind=um[cur_c];
                d2=getDistance(cur_ind,st[i].ind);
                if (mini==0 || d2+dist[cur_ind]!=st[i].d) {
                    location[st[i].ind]=location[st[1].ind]-(st[i].d-st[1].d);
                    stype[st[i].ind]=1;
                    lef.insert(-location[st[i].ind]);
                    mini=st[i].ind;
                } else {
                    location[st[i].ind]=location[cur_ind]+d2;
                    stype[st[i].ind]=2;
                }
            }
        } else {
            l1=location[maxi]-(st[i].d-dist[maxi]);
            cur_c=(*ri.lower_bound(l1));
            cur_ind=um[cur_c];
            d2=getDistance(cur_ind,st[i].ind);
            if (d2+dist[cur_ind]!=st[i].d) {
                location[st[i].ind]=location[0]+st[i].d;
                stype[st[i].ind]=2;
                ri.insert(location[st[i].ind]);
                maxi=st[i].ind;
            } else {
                location[st[i].ind]=location[cur_ind]-d2;
                stype[st[i].ind]=1;
            }
        }
        um[location[st[i].ind]]=st[i].ind;
        //cout << st[i].ind << ' ' << location[st[i].ind] << endl;
    }
}

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