Submission #924549

#	Time	Username	Problem	Language	Result	Execution time	Memory
924549		HuyQuang_re_Zero	Ancient Books (IOI17_books)	C++14	42 / 100	96 ms	42184 KiB

books

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,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)
using namespace std;
#include "books.h"

ll Right[N],Left[N],in[N],ma[N][N],mi[N][N],i,j,l,r,n_cycle,n,p[N],Begin,End,f[N][N],book_move;
II extend[N][N];
const ll oo=round(1e18);
void Init()
{
    for(i=1;i<=n;i++)
        if(in[i]==0)
        {
            n_cycle++;
            l=oo;
            r=-oo;
            for(j=i;in[j]==0;j=p[j])
            {
                in[j]=n_cycle;
                l=min(l,j);
                r=max(r,j);
            }
            Left[n_cycle]=l;
            Right[n_cycle]=r;
        }
    for(i=n;i>=1;i--)
    {
        ma[i][i-1]=-oo;
        mi[i][i-1]=oo;
        for(j=i;j<=n;j++)
        {
            ma[i][j]=max(ma[i][j-1],Right[in[j]]);
            mi[i][j]=min(mi[i][j-1],Left[in[j]]);
        }
    }
}
II Fix(int l,int r)
{
    if(extend[l][r].fst>-1) return extend[l][r];
    if(ma[l][r]>r) return extend[l][r]=Fix(l,ma[l][r]);
    if(mi[l][r]<l) return extend[l][r]=Fix(mi[l][r],r);
    return extend[l][r]={ l,r };
}
ll cal(int l,int r)
{
    II k=Fix(l,r);
    l=k.fst; r=k.snd;
    if(l==Begin && r==End) return 0;
    if(f[l][r]>-1) return f[l][r];
    f[l][r]=oo;
    if(l>Begin) f[l][r]=cal(l-1,r)+2;
    if(r<End) f[l][r]=min(f[l][r],cal(l,r+1)+2);
    return f[l][r];
}
ll minimum_walk(vector <int> _p,int s)
{
    s++;
    for(int k:_p) p[++n]=k,p[n]++;
    for(i=1;i<=n;i++)
    {
        book_move+=abs(i-p[i]);
        if(i!=p[i])
        {
            if(Begin==0) Begin=i;
            End=i;
        }
    }
    if(Begin==0) return 0;
    Begin=min(Begin,(ll)s);
    End=max(End,(ll)s);
    Init();
    memset(f,-1,sizeof(f));
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) extend[i][j]={ -1,-1 };
    return book_move+cal(s,s);
}

/*
int main()
{
    freopen("books.inp","r",stdin);
    freopen("books.out","w",stdout);
    vector <int> p;
    int n,s,k;
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>k,p.push_back(k);
    cout<<minimum_walk(p,s);
}
*/

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30