Submission #1218245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218245		Hamed_Ghaffari	Rail (IOI14_rail)	C++20	100 / 100	212 ms	27864 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 5003;

int d_[MXN][MXN];

inline int d(int i, int j) {
    if(i>j) swap(i, j);
    if(d_[i][j]) return d_[i][j];
    return d_[i][j] = getDistance(i, j);
}

void findLocation(int n, int fir, int x[], int s[]) {
    x[0] = fir;
    fill(s, s+n, 0);
    s[0] = 1;
    if(n==1) return;
    int L=0, R = -1;
    int mn = 1e9;
    for(int i=1; i<n; i++)
        if(d(0, i) < mn) {
            mn = d(0, i);
            R = i;
        }
    s[R] = 2;
    x[R] = x[0] + d(0, R);
    for(int t=0, i, k; t<n-2; t++) {
        i = -1;
        for(int j=0; j<n; j++)
            if(!s[j] && (i==-1 || d(0, i)>d(0,j)))
                i=j;
        x[i] = x[L] + d(L, i);
        k = L;
        for(int j=0; j<n; j++)
            if(s[j]==1 && x[j]>x[k] && x[j]<x[i])
                k=j;
        if(x[i] < x[0] && d(R, i) == x[i] + x[R] - 2*x[k]) {
            s[i] = 2;
            continue;
        }

        x[i] = x[R] - d(R, i);
        k = R;
        for(int j=0; j<n; j++)
            if(s[j]==2 && x[j]<x[k] && x[j]>x[i])
                k=j;
        if(x[i] > x[0] && d(L, i) == 2*x[k] - x[i] - x[L]) {
            s[i] = 1;
            continue;
        }

        k = -1;
        for(int j=0; j<n; j++)
            if(s[j]==2 && x[L]<x[j] && x[j]<x[0])
                k = j;
        if(k!=-1) {
            if(d(i, L) - d(i, 0) == x[0]-x[L]) {
                s[i] = 2;
                x[i] = x[L] + d(L, i);
                R = i;
            }
            else {
                s[i] = 1;
                x[i] = x[R] - d(R, i);
                L = i;
            }
            continue;
        }

        x[i] = x[R] - d(i, R);
        k = R;
        for(int j=0; j<n; j++)
            if(s[j]==2 && x[j]<x[k] && x[j]>x[0])
                k=j;
        if(x[i] < x[L] && d(i, 0) == 2*x[k] - x[0] - x[i]) {
            s[i] = 1;
            L = i;
            continue;
        }

        s[i] = 2;
        x[i] = x[L] + d(L, i);
        R = i;
    }
}

/*

L   k   i   0   R
(   (   )   (   )

if( x[L] + d(L, i) < x[0])
    if( d(R, i) == x[L] + d(L, i) + x[R] - 2*x[k])
        ok

L   0   i   k   R
(   (   (   )   )

if( x[R] - d(R, i) > x[0])
    if( d(L, i) == 2*x[k] - x[L] - (x[R] - d(R, i)))
        ok


if {

L   ?   0   r
(   )   (   )

if( d(i, L) - d(i, 0) == x[0]-x[L] ) 4
else 1

}
else {

i   L   0   k   R
(   (   (   )   )

if( x[R] - d(i, R) < x[L])
    if( d(i, 0) == 2*x[k] - x[0] - (x[R] - d(i, R)))
        ok

}
*/

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