oj.uz

Submission #924549

# Submission time Handle Problem Language Result Execution time Memory
924549 2024-02-09T07:40:55 Z HuyQuang_re_Zero Ancient Books (IOI17_books) C++14
42 / 100
 96 ms 42184 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 2 ms 10332 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 2 ms 10332 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 9 ms 39516 KB Output is correct
20 Correct 7 ms 39516 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 8 ms 39772 KB Output is correct
23 Correct 7 ms 39692 KB Output is correct
24 Correct 7 ms 39620 KB Output is correct
25 Correct 8 ms 39772 KB Output is correct
26 Correct 9 ms 39512 KB Output is correct
27 Correct 7 ms 39516 KB Output is correct
28 Correct 7 ms 39516 KB Output is correct
29 Correct 8 ms 39516 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 2 ms 10332 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 9 ms 39516 KB Output is correct
20 Correct 7 ms 39516 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 8 ms 39772 KB Output is correct
23 Correct 7 ms 39692 KB Output is correct
24 Correct 7 ms 39620 KB Output is correct
25 Correct 8 ms 39772 KB Output is correct
26 Correct 9 ms 39512 KB Output is correct
27 Correct 7 ms 39516 KB Output is correct
28 Correct 7 ms 39516 KB Output is correct
29 Correct 8 ms 39516 KB Output is correct
30 Runtime error 96 ms 42184 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 39772 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 8 ms 39772 KB Output is correct
4 Correct 9 ms 39796 KB Output is correct
5 Correct 9 ms 39772 KB Output is correct
6 Correct 8 ms 39656 KB Output is correct
7 Correct 9 ms 39512 KB Output is correct
8 Correct 8 ms 39512 KB Output is correct
9 Correct 8 ms 39512 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 8 ms 39772 KB Output is correct
12 Correct 8 ms 39560 KB Output is correct
13 Correct 7 ms 39512 KB Output is correct
14 Correct 7 ms 39516 KB Output is correct
15 Correct 7 ms 39516 KB Output is correct
16 Correct 7 ms 39516 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 8 ms 39768 KB Output is correct
19 Correct 8 ms 39516 KB Output is correct
20 Correct 8 ms 39572 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10332 KB Output is correct
7 Correct 2 ms 10332 KB Output is correct
8 Correct 2 ms 10332 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 10332 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 10332 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 9 ms 39516 KB Output is correct
20 Correct 7 ms 39516 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 8 ms 39772 KB Output is correct
23 Correct 7 ms 39692 KB Output is correct
24 Correct 7 ms 39620 KB Output is correct
25 Correct 8 ms 39772 KB Output is correct
26 Correct 9 ms 39512 KB Output is correct
27 Correct 7 ms 39516 KB Output is correct
28 Correct 7 ms 39516 KB Output is correct
29 Correct 8 ms 39516 KB Output is correct
30 Runtime error 96 ms 42184 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -