Submission #1102143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102143		alexander707070	Rail (IOI14_rail)	C++14	30 / 100	45 ms	4680 KiB

rail

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

#define MAXN 1000007
using namespace std;

int n,pos,fr;
pair<int,int> block[MAXN];
pair<int,int> dist[5007];
int last;

vector<int> clos,opos;
int sum[MAXN];

void findLocation(int N, int first, int location[], int stype[]){
    n=N;
    block[first]={0,0};

    location[0]=first;
    stype[0]=1;

    for(int i=1;i<n;i++){
        dist[i].first=getDistance(0,i);
        dist[i].second=i;
    }

    sort(dist+1,dist+n);

    last=1; fr=0;
    location[dist[1].second]=first+dist[1].first;
    stype[dist[1].second]=2;

    clos.push_back(1);
    opos.push_back(0);

    for(int i=2;i<n;i++){

        int curr=getDistance(dist[i].second,dist[last].second);
        int where=location[dist[last].second]-curr;

        int curr2=getDistance(dist[i].second,dist[fr].second);
        int where2=location[dist[fr].second]+curr2;
        
        int nearest=last;
        for(int f:clos){
            if(location[dist[f].second]>where and location[dist[f].second]<location[dist[nearest].second]){
                nearest=f;
            }
        }

        if(dist[i].first==dist[nearest].first+(location[dist[nearest].second]-where)){
            location[dist[i].second]=where;
            stype[dist[i].second]=1;
        }else{
            location[dist[i].second]=where2;
            stype[dist[i].second]=2;
        }

        if(location[dist[i].second]>location[dist[last].second]){
            last=i;
            clos.push_back(i);
        }

        if(location[dist[i].second]<location[dist[fr].second]){
            fr=i;
            opos.push_back(i);
        }
    }

    return;
}

/*
3
8
1 0
2 2
1 3
2 5
2 6
1 7
1 8
2 10


*/

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