oj.uz

답안 #872549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872549 2023-11-13T10:58:30 Z HuyQuang_re_Zero 철로 (IOI14_rail) C++14
100 / 100
 51 ms 4892 KB 
#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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4688 KB Output is correct
2 Correct 47 ms 4648 KB Output is correct
3 Correct 49 ms 4688 KB Output is correct
4 Correct 45 ms 4688 KB Output is correct
5 Correct 45 ms 4688 KB Output is correct
6 Correct 45 ms 4692 KB Output is correct
7 Correct 46 ms 4692 KB Output is correct
8 Correct 45 ms 4632 KB Output is correct
9 Correct 45 ms 4692 KB Output is correct
10 Correct 45 ms 4692 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4692 KB Output is correct
2 Correct 45 ms 4688 KB Output is correct
3 Correct 44 ms 4692 KB Output is correct
4 Correct 45 ms 4688 KB Output is correct
5 Correct 45 ms 4648 KB Output is correct
6 Correct 46 ms 4692 KB Output is correct
7 Correct 51 ms 4692 KB Output is correct
8 Correct 45 ms 4692 KB Output is correct
9 Correct 45 ms 4652 KB Output is correct
10 Correct 45 ms 4688 KB Output is correct
11 Correct 45 ms 4688 KB Output is correct
12 Correct 44 ms 4688 KB Output is correct
13 Correct 45 ms 4652 KB Output is correct
14 Correct 45 ms 4696 KB Output is correct
15 Correct 45 ms 4688 KB Output is correct
16 Correct 45 ms 4648 KB Output is correct
17 Correct 45 ms 4648 KB Output is correct
18 Correct 44 ms 4892 KB Output is correct
19 Correct 47 ms 4652 KB Output is correct
20 Correct 45 ms 4692 KB Output is correct