Submission #827390

#	Time	Username	Problem	Language	Result	Execution time	Memory
827390		Trunkty	Rail (IOI14_rail)	C++14	30 / 100	44 ms	524 KiB

rail

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "rail.h"

int dist0[5005],mval=2e9,mpos,distm[5005];

void findLocation(int n, int f, int location[], int stype[]){
    if(n==1){
        location[0] = f;
        stype[0] = 1;
        return;
    }
    for(int i=1;i<=n-1;i++){
        dist0[i] = getDistance(0,i);
        if(dist0[i]<mval){
            mval = dist0[i];
            mpos = i;
        }
    }
    for(int i=0;i<=n-1;i++){
        if(i!=mpos){
            distm[i] = getDistance(mpos,i);
        }
    }
    location[0] = f;
    location[mpos] = f+dist0[mpos];
    stype[0] = 1;
    stype[mpos] = 2;
    vector<pair<int,int>> lef,rit;
    for(int i=1;i<=n-1;i++){
        if(i!=mpos){
            if(distm[i]<=dist0[mpos]){
                location[i] = location[mpos]-distm[i]; 
                stype[i] = 1;
            }
            else if(dist0[i]>distm[i]){
                lef.push_back({distm[i],i});
            }
            else{
                rit.push_back({dist0[i],i});
            }
        }
    }
    sort(lef.begin(),lef.end());
    sort(rit.begin(),rit.end());
    int maxc = 0;
    for(pair<int,int> i:lef){
        if(getDistance(maxc,i.second)>i.first){
            maxc = i.second;
            location[i.second] = location[mpos]-i.first;
            stype[i.second] = 1;
        }
        else{
            location[i.second] = location[mpos]-i.first;
            stype[i.second] = 2;
        }
    }
    int maxd = mpos;
    for(pair<int,int> i:rit){
        if(getDistance(maxd,i.second)>i.first){
            maxd = i.second;
            location[i.second] = f+i.first;
            stype[i.second] = 2;
        }
        else{
            location[i.second] = f+i.first;
            stype[i.second] = 1;
        }
    }
}

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