Submission #581523

#	Time	Username	Problem	Language	Result	Execution time	Memory
581523		wdjpng	Rail (IOI14_rail)	C++17	30 / 100	154 ms	196424 KiB

rail

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

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

void findLocation(signed n, signed first, signed lo[], signed sty[])
{
    vector<vector<int>>dist(n, vector<int>(n));
    vector<int>location(n);
    vector<int>stype(n);

    vector<int>d0(n);
    int minn=1e12,mini=-1;
    for(int i = 1; i < n; i++) {
        int d = d0[i] = getDistance(0,i);
        if(d<minn) {minn=d; mini=i;}
    }

    vector<int>dmini(n);
    dmini[0]=d0[mini];
    rep(i,n) if(i!=0&&i!=mini) dmini[i]=getDistance(i,mini);
    int l=-1, maxl=0, r=-1, maxr=0;
    rep(i,n)
    {
        if(d0[i]<dmini[i]&&maxr<d0[i]) 
        {
            maxr= d0[i];
            r=i;
        } 
        if(dmini[i]<d0[i]&&maxl<dmini[i])
        {
            maxl=dmini[i];
            l=i;
        }
    }

    if(l==-1) l=0;
    if(r==-1) r=mini;

    stype[0]=1;
    stype[mini]=2;
    location[0]=first;
    location[mini]=first+d0[mini];
    stype[r]=2;
    stype[l]=1;
    location[l]=location[mini]-dmini[l];
    location[r]=location[0]+d0[r];

    rep(i,n) {
        if(i==0||i==mini||i==r||i==l) continue;
        if(dmini[i]<d0[i])
        {
            int dist_to_l = getDistance(i,l);
            if(dist_to_l+dmini[l]==dmini[i])
            {
                stype[i]=2;
                location[i]=location[l]+dist_to_l;
            } else {
                stype[i]=1;
                location[i]=location[mini]-dmini[i];
            }
        } else 
        {
            int dist_to_r = getDistance(i,r);
            if(dist_to_r+d0[r]==d0[i])
            {
                stype[i]=1;
                location[i]=location[r]-dist_to_r;
            } else {
                stype[i]=2;
                location[i]=location[0]+d0[i];
            }
        }
    }
    rep(i,n) sty[i]=stype[i];
    rep(i,n) lo[i]=location[i];
}

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