oj.uz

답안 #638804

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
638804 2022-09-07T14:10:02 Z qwerasdfzxcl 고대 책들 (IOI17_books) C++17
22 / 100
 2000 ms 13600 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -