제출 #872533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872533		HuyQuang_re_Zero	철로 (IOI14_rail)	C++14	0 / 100	57 ms	9552 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[1505],f[1505][1505];
    void Init(int n,int x[],int type[])
    {
        for(i=0;i<n;i++) node[i]=i;
        sort(node,node+n,[&](int u,int v){ return x[u]<x[v]; });
        memset(f,63,sizeof(f));
        for(u=0;u<n;u++) f[u][u]=0;
        for(i=0;i<n;i++)
        {
            u=node[i];
            for(j=i+1;j<n;j++)
            {
                v=node[j];
                if(type[u]==1 && type[v]==2) f[u][v]=f[v][u]=x[v]-x[u];
            }
        }
        for(k=0;k<n;k++)
            for(u=0;u<n;u++)
                for(v=0;v<n;v++) f[u][v]=min(f[u][v],f[u][k]+f[k][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.f[u][v];
}*/
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;
    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';

    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: 0 / 8
• Subtask 2: 0 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44