Submission #638804

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638804	2022-09-07T14:10:02 Z	qwerasdfzxcl	Ancient Books (IOI17_books)	C++17	22 / 100	2000 ms	13600 KB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int  n, s, ts, ans, a[1001000], cycL[1001000], cycR[1001000], L[1001000], R[1001000], dp[1001000];
bool visited[1001000];
ll cycsum;

struct Seg{
    int tree[2002000], sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, 1e9);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    int query(int l, int r){
        int ret = 1e9;
        ++r;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}tree;

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}


void dfs(int l, int r){
    //printf("dfs: %d %d\n", l, r);
    if (l==L[ts] && r==R[ts]) {ans += dp[L[ts]]; return;}

    vector<pair<int, int>> child;
    for (int i=l+1;i<r;){
        if (R[i]<r){
            child.emplace_back(i, R[i]);
            i = R[i] + 1;
        }
        else i++;
    }

    vector<int> gl = {1}, gr = {1};
    for (int i=1;i<(int)child.size();i++){
        if (child[i-1].second+1==child[i].first) gl.push_back(gl.back()+1);
        else gl.push_back(1);
    }
    for (int i=(int)child.size()-2;i>=0;i--){
        if (child[i].second+1==child[i+1].first) gr.push_back(gr.back()+1);
        else gr.push_back(1);
    }
    reverse(gr.begin(), gr.end());

    for (int i=0;i<(int)child.size();i++) dp[child[i].first] = min(gl[i], gr[i]);
    if (l==0) for (int i=0;i<(int)child.size();i++) dp[child[i].first] = (int)child.size()-1;

    for (auto &[nl, nr]:child) dfs(nl, nr);
}

void naive(int s){
    fill(visited+1, visited+n+1, 0);
    int mn = s;
    int mx = s;

    int ptl = s, ptr = s;

    while(mn <= ptl || ptr <= mx){
        int j = -1;

        if (mn <= ptl){
            if (visited[ptl]) {--ptl; continue;}
            j = ptl--;
        }
        else{
            if (visited[ptr]) {++ptr; continue;}
            j = ptr++;
        }

        for (;!visited[j];j=a[j]){
            visited[j] = 1;
            mn = min(mn, j);
            mx = max(mx, j);
        }
    }

    L[s] = mn, R[s] = mx;
}

long long minimum_walk(std::vector<int> P, int S) {
    int si = 0, ei = (int)P.size()-1;
    for(;si<(int)P.size() && P[si]==si;si++);
    for(;ei>=0 && P[ei]==ei;ei--);

    if (si > ei) return 0;
    n = ei-si+1;
    for (int i=si;i<=ei;i++) a[i-si+1] = P[i] - si + 1;
    s = S-si+1;

    for (int i=1;i<=n;i++) if (!visited[i]){
        for (int j=i;!visited[j];j=a[j]){
            visited[j] = 1;
            cycR[i] = max(cycR[i], j);
            cycsum += myabs(j - a[j]);
        }
        cycL[cycR[i]] = i;
    }

    ///calc range
    for (int i=1;i<=n;i++) naive(i);

    /*for (int i=1;i<=n;i++) printf("(%d, %d) ", cycL[i], cycR[i]);
    printf("\n");
    for (int i=1;i<=n;i++) printf("(%d, %d) ", L[i], R[i]);
    printf("\n");*/

    if (s<=0) ts = 1, ans = 1-s;
    else if (s>n) ts = n, ans = s-n;
    else ts = s, ans = 0;

    //printf("ok n = %d, s = %d\n", n, s);
    dfs(0, n+1);

    return cycsum + ans * 2;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	4 ms	340 KB	Output is correct
20	Correct	5 ms	340 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Execution timed out	2031 ms	13600 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Incorrect	1 ms	308 KB	3rd lines differ - on the 1st token, expected: '22140', found: '22128'
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	4 ms	340 KB	Output is correct
20	Correct	5 ms	340 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Execution timed out	2031 ms	13600 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Submission #638804

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0