Submission #872549

#	Time	Username	Problem	Language	Result	Execution time	Memory
872549		HuyQuang_re_Zero	Rail (IOI14_rail)	C++14	100 / 100	51 ms	4892 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;

struct Interactive
{
    int n,i,j,k,u,v,node[5005],pos[5005],x[5005],type[5005];
    void Init(int _n,int _x[],int _type[])
    {
        n=_n;
        for(i=0;i<n;i++) node[i]=i,x[i]=_x[i],type[i]=_type[i];
        sort(node,node+n,[&](int u,int v){ return x[u]<x[v]; });
        for(i=0;i<n;i++) pos[node[i]]=i;
    }
    int get(int u,int v)
    {
        if(x[u]>x[v]) swap(u,v);
        int uu,vv;
        if(type[u]==2)
        {
            for(i=pos[u];i>=0;i--)
                if(type[node[i]]==1) break;
            uu=node[i];
        }
        if(type[v]==1)
        {
            for(i=pos[v];i<n;i++)
                if(type[node[i]]==2)
                    break;
            vv=node[i];
        }
        if(type[u]==1 && type[v]==2) return x[v]-x[u];
        if(type[u]==2 && type[v]==2) return x[u]-x[uu]+x[v]-x[uu];
        if(type[u]==1 && type[v]==1) return x[vv]-x[v]+x[vv]-x[u];
        return x[u]-x[uu]+x[vv]-x[uu]+x[vv]-x[v];
    }

} IR;
int x[5005],type[5005],mask[1000005],n,i,u,v,dis0[5005],disk[5005],to_l,to_r,x0,k;
II a[5005];
/*
int getDistance(int u,int v)
{
  //  cerr<<u<<" "<<v<<'\n';
    return IR.get(u,v);
}

*/
void findLocation(int n,int x0,int x[],int type[])
{
    auto add=[&](int u,int _x,int _type)
    {
        x[u]=_x;
        type[u]=_type;
        mask[x[u]]=type[u];
    };
    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);
    }
  //  cerr<<dis0[3]<<" "<<disk[3]<<" "<<dis0[k]<<'\n';
    int l=0,r=k;
    for(i=2;i<n;i++)
    {
        u=a[i].snd;
       // cerr<<l<<" "<<r<<" "<<u<<'\n';
      //  cerr<<u<<'\n';
        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,x[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,x[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;
    for(i=0;i<n;i++) cin>>type[i]>>x[i];
    IR.Init(n,x,type);
    x0=x[0];
    memset(x,0,sizeof(x));
    memset(type,0,sizeof(type));
    findLocation(n,x0,x,type);
    for(i=0;i<n;i++) cout<<x[i]<<" "<<type[i]<<'\n';

  //  return 0;

    freopen("rail.inp","r",stdin);
    cin>>n;
    for(i=0;i<n;i++)
    {
        int T,X;
        cin>>T>>X;
        if(T!=type[i] || X!=x[i])
            cerr<<i<<'\n';
    }
}

*/

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