Submission #1102116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102116		alexander707070	Rail (IOI14_rail)	C++14	0 / 100	40 ms	668 KiB

rail

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

#define MAXN 1000007
using namespace std;

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

vector<int> clos;
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;
    location[dist[1].second]=first+dist[1].first;
    stype[dist[1].second]=2;

    for(int i=2;i<n;i++){
        if(dist[last].first+dist[i].first == getDistance(dist[last].second,dist[i].second)){
            last=i;

            stype[dist[i].second]=2;
            location[dist[i].second]=first+dist[i].first;
        }
    }

    int special=dist[last].second;
    int fin=location[special];

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

    sort(dist,dist+n);

    last=1;
    location[dist[1].second]=fin-dist[1].first;
    stype[dist[1].second]=1;
    clos.push_back(1);
    
    for(int i=2;i<n;i++){
        if(dist[last].first+dist[i].first == getDistance(dist[last].second,dist[i].second)){
            last=i;

            stype[dist[i].second]=1;
            location[dist[i].second]=fin-dist[i].first;
            clos.push_back(i);
        }else{
            for(int f:clos){
                if(dist[i].first-dist[f].first<=sum[f])continue;

                if(dist[f].first+getDistance(dist[f].second,dist[i].second)==dist[i].first){
                    location[dist[i].second]=dist[f].first+(dist[i].first-dist[f].first);
                    stype[dist[i].second]=2;
                    sum[f]=(dist[i].first-dist[f].first);
                    break;
                }
            }
        }
    }

    return;
}

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