oj.uz

Submission #938138

# Submission time Handle Problem Language Result Execution time Memory
938138 2024-03-04T22:12:00 Z snpmrnhlol Ancient Books (IOI17_books) C++17
0 / 100
 2 ms 4444 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 2e9;
bool vis[N];
vector <int> points;
int l[N],r[N];
long long minimum_walk(std::vector<int> p, int s) {
    int n = p.size();
    ll ans = 0;
    ll mn2 = s;
    ll mx2 = s;
    for(ll i = 0;i < n;i++){
        ans+=abs(i - p[i]);
        if(i != p[i]){
            mx2 = max(mx2,i);
            mn2 = min(mn2,i);
        }
        if(!vis[i]){
            points.clear();
            int nr = i;
            int mx = -inf;
            int mn = inf;
            while(!vis[nr]){
                vis[nr] = 1;
                mx = max(mx,nr);
                mn = min(mn,nr);
                points.push_back(nr);
                nr = p[nr];
            }
            for(auto j:points){
                l[j] = mn;
                r[j] = mx;
            }
        }
    }
    int curl,curr,exl,exr;
    curl = s;exl = l[s];
    curr = s;exr = r[s];
    //cout<<mn2<<' '<<mx2<<' '<<exl<<' '<<exr<<' '<<curl<<' '<<curr<<'\n';
    while(exl > mn2 || exr < mx2){
        if(curl > exl){
            curl--;
            exl = min(exl,l[curl]);
            exr = max(exr,r[curl]);
        }else if(curr < exr){
            curr++;
            exl = min(exl,l[curr]);
            exr = max(exr,r[curr]);
        }else{
            int costl = 0;
            bool ok = 0;
            int x = exl;
            int exl2 = exl;
            while(x > mn2){
                if(r[x] > exr){
                    ok = 1;
                    break;
                }
                exl2 = min(exl2,l[x]);
                if(x == exl2){
                    costl+=2;
                    exl2--;
                }
                x--;
            }
            int costr = 0;
            int exr2 = exr;
            x = exr;
            while(x < mx2){
                if(l[x] < exl){
                    ok = 1;
                    break;
                }
                exr2 = max(exr2,r[x]);
                if(x == exr2){
                    costr+=2;
                    exr2++;
                }
                x++;
            }
            if(ok){
                if(costl > costr){
                    exr = exr2;
                    ans+=costr;
                }else{
                    exl = exl2;
                    ans+=costl;
                }
            }else{
                ans+=costl;
                ans+=costr;
                break;
            }
        }
    }
    cout<<ans<<'\n';
	return ans;
}
/**
7 3
6 1 2 3 4 5 0
7 3
2 1 0 3 6 5 4
**/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4444 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB secret mismatch
2 Halted 0 ms 0 KB -