Submission #872520

#	Time	Username	Problem	Language	Result	Execution time	Memory
872520		HuyQuang_re_Zero	Rail (IOI14_rail)	C++14	0 / 100	3057 ms	644 KiB

rail

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "rail.h"
using namespace std;


int x[1505],type[1505],mask[1000005],n,i,u,v,dis0[1505],disk[1505],to_l,to_r,x0,k;
II a[1505];
/*
int getDistance(int u,int v)
{
    cout<<u<<" "<<v<<'\n';
    int k;
    cin>>k;
    return k;
}*/
void add(int u,int _x,int _type)
{
    x[u]=_x;
    type[u]=_type;
    mask[x[u]]=type[u];
}
void findLocation(int n,int x0,int x[],int type[])
{
    for(i=1;i<n;i++) a[i]={ getDistance(i,0),i };
    sort(a+1,a+n);
    add(0,x0,1);
    add(a[1].snd,x0+a[1].fst,2);
    k=a[1].snd;
    for(i=0;i<n;i++)
    {
        dis0[a[i].snd]=a[i].fst;
        if(i==k) disk[i]=0;
        else if(i==0) disk[i]=a[1].fst;
        else disk[i]=getDistance(i,k);
    }
    int l=0,r=k;
    for(i=2;i<n;i++)
    {
        u=a[i].snd;
        if(dis0[u]==disk[u]+dis0[k] && disk[u]<disk[0])
            add(u,x[k]-disk[u],1);
        else if(dis0[u]==disk[u]+dis0[k])
        {
            int tg=disk[u]-disk[l]-(to_l=getDistance(l,u));
            int ttv=mask[x[l]-tg/2];
            if(ttv==1) add(u,l+to_l,2);
            else add(u,x[k]-disk[u],1);
        }
        else
        {
            int tg=dis0[u]-dis0[r]-(to_r=getDistance(r,u));
            int ttv=mask[x[r]+tg/2];
            if(ttv==2) add(u,r-to_r,1);
            else add(u,x[0]+dis0[u],2);
        }
        if(x[l]>x[u]) l=u;
        if(x[r]<x[u]) r=u;
    }
}
/*
int main()
{
 //   freopen("rail.inp","r",stdin);
   // freopen("rail.out","w",stdout);
    cin>>n>>x0;
    findLocation(n,x0,x,type);
    for(i=0;i<n;i++) cout<<x[i]<<" "<<type[i]<<'\n';
}
*/

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