Submission #713549

#	Time	Username	Problem	Language	Result	Execution time	Memory
713549		lam	Rail (IOI14_rail)	C++14	30 / 100	187 ms	199740 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int d[maxn][maxn];
int n;
int a[maxn];
int ans[maxn];
inline int calc(int u, int v)
{
    if (u>v) swap(u,v);
    if (d[u][v] == -1) d[u][v] = getDistance(u,v);
    return d[u][v];
}
bool cmp(int x, int y)
{
    return calc(0,x)<calc(0,y);
}
void findLocation(int N, int first, int location[], int stype[])
{
    n=N;
    for (int i=0; i<n; i++) stype[i] = ans[i] = -1;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) d[i][j] = -1;
    ans[0] = first;
    for (int i=1; i<n; i++)
    {
        int temp = calc(0,i);
        a[i] = i;
    }
    ans[0] = first;
    sort(a+1,a+n,cmp);
    int L = 0; int R = a[1];
    ans[R] = ans[L] + calc(L,R);
    stype[R] = 1;
    stype[L] = 0;
//    cerr<<first<<' '<<n<<endl;
    for (int i=2; i<n; i++)
    {
        int val = calc(L,a[i]);
//        cerr<<L<<','<<ans[L]<<' '<<R<<','<<ans[R]<<" = "<<a[i]<<'\n';
        /** L k R
            ( ) )  **/
        int pos = ans[L] + val;
//        cerr<<pos<<"!!\n";
        if (pos<ans[R])
        {
            int p = -1;
            for (int j=0; j<n; j++)
                if (ans[j]!=-1&&stype[j]==0&&ans[p]<pos&&(p==-1||ans[p] < ans[j])) p = j;
            if (p!=-1&&calc(a[i],R) == pos - ans[p] + ans[R] - ans[p])
            {
                ans[a[i]] = pos;
                stype[a[i]] = 1;
                continue;
            }
        }
        else /**
            L R k
            ( ) )
            **/
        {
            int p = -1;
//            for (int j=0; j<n; j++) cerr<<ans[j]<<":"<<stype[j]<<" "; cerr<<'\n';
            for (int j=0; j<n; j++)
                if (ans[j]!=-1&&stype[j]==0&&ans[p]<R&&(p==-1||ans[p] < ans[j])) p = j;
//            cerr<<p<<endl;
            if (p!=-1&&calc(a[i],R) == pos - ans[p] + ans[R] - ans[p])
            {
                ans[a[i]] = pos;
                stype[a[i]] = 1;
                R = a[i];
                continue;
            }
//            cerr<<":<"<<endl;
        }
        val = calc(a[i],R);
        pos = ans[R] - val;
//        cerr<<val<<' '<<pos<<" @@ "<<endl;
        /** L k R
            ( (  ) **/
        if (pos > ans[L])
        {
            int p = -1;
            for (int j=0; j<n; j++)
                if (ans[j]!=-1&&ans[j] > pos&&stype[j]==1&&(p==-1||ans[p] > ans[j])) p=j;
            if (p!=-1&&calc(a[i],L) == 2*ans[p] - pos - ans[L])
            {
                ans[a[i]]=pos;
                stype[a[i]] = 0;
                continue;
            }
        }
        else/**
            k L R
            ( ( )
            **/
        {
            int p = -1;
            for (int j=0; j<n; j++)
                if (ans[j]!=-1&&ans[j] > ans[L]&&stype[j]==1&&(p==-1||ans[p] > ans[j])) p=j;
            if (p!=-1&&calc(a[i],L) == 2*ans[p] - pos - ans[L])
            {
                ans[a[i]]=pos;
                stype[a[i]] = 0;
                L = a[i];
                continue;
            }
        }
        assert(false);
    }
    for (int i=0; i<n; i++) stype[i] ++;
    ans[0] = first;
    for (int i=0; i<n; i++) location[i] = ans[i];
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:13: warning: unused variable 'temp' [-Wunused-variable]
   29 |         int temp = calc(0,i);
      |             ^~~~

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