Submission #70337

#	Time	Username	Problem	Language	Result	Execution time	Memory
70337		yusufake	Rail (IOI14_rail)	C++98	30 / 100	88 ms	960 KiB

rail

#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
 
#define mp make_pair
#define st first
#define nd second
#define mxx 10004
pair < int , int > T[mxx];
int L[mxx],R[mxx],l,r,El[mxx],Er[mxx],UU[mxx];
void findLocation(int n, int x, int *A, int *B){
    int i,j,y,z,u,uu,t,tt,mn;
    A[0] = x;
    B[0] = 1;
    for(i=1;i<n;i++)
        T[i] = mp(abs(getDistance(0,i)),i);
    sort(T+1,T+n);
    y = T[1].nd;
    A[y] = x+T[1].st;
    B[y] = 2;
    x = 0;
    R[0] = y;
    L[0] = x;
    memset(El,-1,sizeof El);
    memset(Er,-1,sizeof Er);
    El[0] = A[y];
    mn = T[1].st;
    for(i=2;i<n;i++){
        z = T[i].nd;
        UU[i] = abs(getDistance(y,z));
        if(mn > UU[i]) mn = UU[i];
    }
    Er[0] = A[y]-mn;
    //cout << x << " " << A[x] << " aa\n";
    //cout << y << " " << A[y] << " bb\n";
    for(i=2;i<n;i++){
        u = T[i].st;
        z = T[i].nd;
        if(u != T[1].st + (uu=UU[i])){
            if(!r){
                A[z] = A[x]+u;
                B[z] = 2;
                R[++r] = z;
                continue;
            }
            t = abs(getDistance(z,R[r]));
            for(j=r; j ; j--)
                if(Er[j] != -1) break;
            //cout << z << " " << R[r] << " " << t << " " << j << " " << Er[0] << " " << A[x]+u-Er[j] + R[r]-Er[j] << " aa\n";
            if(t == A[x]+u-Er[j] + A[ R[r] ]-Er[j]){
                A[z] = A[x]+u;
                B[z] = 2;
                R[++r] = z;
                continue;
            }
            for(j=1;j<=r;j++)
                if((tt=A[ R[j] ]-(u-(A[ R[j] ]-A[x]))) > A[ R[j-1] ] && t == A[ R[r] ]-tt){
                    A[z] = tt;
                    B[z] = 1;
                    if(Er[j] == -1) Er[j] = A[z];
                    break;
                }
        }
        else{
            if(A[y]-uu > A[x]){
                A[z] = A[y]-uu;
                B[z] = 1;
                continue;
            }
            if(!l){
                A[z] = A[y]-uu;
                B[z] = 1;
                L[++l] = z;
                continue;
            }
            t = abs(getDistance(z,L[l]));
            for(j=l; j ; j--)
                if(El[j] != -1) break;
            if(t == El[j]-(A[y]-uu) + El[j]-A[ L[l] ]){
                A[z] = A[y]-uu;
                B[z] = 1;
                L[++l] = z;
                continue;
            }
            for(j=1;j<=l;j++)
                if((tt=A[ L[j] ]+(uu-(A[y]-A[ L[j] ]))) < A[ L[j-1] ] && t == A[ L[l] ]-tt){
                    A[z] = tt;
                    B[z] = 2;
                    if(El[j] == -1) El[j] = A[z];
                    break;
                }
        }
    }
 
}

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