Submission #581501

#	Time	Username	Problem	Language	Result	Execution time	Memory
581501		wdjpng	Rail (IOI14_rail)	C++17	30 / 100	189 ms	196428 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);

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

    int l=-1, maxl=0, r=-1, maxr=0;
    rep(i,n)
    {
        if(getDistance(0,i)<getDistance(mini,i)&&maxr<getDistance(0,i)) 
        {
            maxr= getDistance(0,i);
            r=i;
        } 
        if(getDistance(mini,i)<getDistance(0,i)&&maxl<getDistance(mini,i))
        {
            maxl=getDistance(mini,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+getDistance(0,mini);
    stype[r]=2;
    stype[l]=1;
    location[l]=location[mini]-getDistance(l,mini);
    location[r]=location[0]+getDistance(0,r);

    rep(i,n) {
        if(i==0||i==mini||i==r||i==l) continue;
        int d0 = getDistance(i,0), dmini = getDistance(i,mini);
        if(dmini<d0)
        {
            if(getDistance(i,l)+getDistance(l,mini)==dmini)
            {
                stype[i]=2;
                location[i]=location[l]+getDistance(i,l);
            } else {
                stype[i]=1;
                location[i]=location[mini]-dmini;
            }
        } else 
        {
            if(getDistance(i,r)+getDistance(r,0)==d0)
            {
                stype[i]=1;
                location[i]=location[r]-getDistance(i,r);
            } else {
                stype[i]=2;
                location[i]=location[0]+d0;
            }
        }
    }
    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