제출 #65360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65360		theknife2001	철로 (IOI14_rail)	C++17	30 / 100	97 ms	804 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ii pair < int , int >
#define se second
#define fi first


using namespace std;
const int N=5e3+55;
int dist[N];
ii a[N];


void findLocation(int n, int zero, int location[], int stype[])
{
    location[0]=zero;
    stype[0]=1;
    int temp;
    for(int i=1;i<n;i++)
    {
        temp=getDistance(0,i);
        a[i-1]={temp,i};
        dist[i]=temp;
    }
    sort(a,a+n-1);
    int first;
    int second=-1;
    int last;
    int x,y;
    for(int i=0;i<n-1;i++)
    {
        if(!i)
        {
            first=a[i].se;
            last=first;
            location[first]=zero+a[i].fi;
            stype[first]=2;
            continue ;
        }
        x=getDistance(last,a[i].se);
        if(se!=-1)
            y=getDistance(second,a[i].se);
//        if(first!=last)
//            y=getDistance(first,a[i].se);
//        cout<<a[i].se<<' '<<a[i].fi<<' '<<dist[first]<<' '<<x<<' '<<y<<endl;
        if(x+dist[last]==a[i].fi&&(se==-1||dist[second]+y!=a[i].fi))
        {
            if(last==first)
                if(dist[last]<x)
                    second=a[i].se;
            stype[a[i].se]=1;
            location[a[i].se]=location[last]-x;
        }
        else if(x==dist[a[i].se]+dist[last])
        {
            last=a[i].se;
            stype[a[i].se]=2;
            location[a[i].se]=zero+a[i].fi;

        }
        else
        {
            if(second!=-1)
            {
                if(dist[second]+y==a[i].fi)
                {
                    stype[a[i].se]=2;
                    location[a[i].se]=location[second]+y;
                    continue ;
                }
            }
            second=a[i].se;
            stype[a[i].se]=1;
            location[a[i].se]=zero-a[i].fi+2*dist[first];
        }
    }
//    cout<<endl;
//    for(int i=0;i<n;i++)
//        cout<<stype[i]<<' '<<location[i]<<endl;
}

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