oj.uz

Submission #835317

# Submission time Handle Problem Language Result Execution time Memory
835317 2023-08-23T12:49:37 Z jasmin Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 468 KB 
#include "books.h"
#include<bits/stdc++.h>
using namespace std;

const int INF=1e9+7;

long long minimum_walk(std::vector<int> p, int s) {
    int n=p.size();
	
    long long ans=0;
    
    vector<bool> vis(n, false);
    vector<int> cycle(n, -1);
    vector<int> starts(n, -1); //-1: nothing, 0: starts, 1: ends
    for(int i=0; i<n; i++){
        if(vis[i]) continue;

        int v=i;
        int cnt=0;
        int l=i;
        int r=i;
        while(!vis[v]){
            vis[v]=true;
            cycle[v]=i;

            cnt++;
            l=min(l, v);
            r=max(r, v);

            ans += abs(p[v]-v);
            v=p[v];
        }

        if(cnt==1 && i!=s){
            cycle[i] = -1;
        }
        starts[l]=0;
        starts[r]=1; 
    }

    
    set<int> active;
    vector<bool> unfinished(n, false);
    set<int> good;
    for(int i=0; i<n; i++){
        if(cycle[i]==-1) continue;
        good.insert(i);

        if(starts[i]==0){
            active.insert(cycle[i]);
        }
        if(starts[i]==2 && active.find(cycle[i])!=active.end()){
            active.erase(cycle[i]);

            unfinished[cycle[i]]=true;
        }

        while(!active.empty() && *active.begin() != cycle[i]){
            active.erase(*active.begin());
        }
        while(!active.empty() && *prev(active.end()) != cycle[i]){
            active.erase(*prev(active.end()));
        }
    }

    vector<int> add(n, INF);
    for(int i=0; i<n; i++){
        if(!unfinished[cycle[i]]) continue;
        assert(unfinished[cycle[i]]);

        int a = INF;
        auto it=good.upper_bound(i);
        if(it!=good.end()){
            a = min(a, 2*(*it - i));
        }
        if(it!=good.begin()){
            a = min(a, 2*(i - *it));
        }
        
        add[cycle[i]] = min(add[cycle[i]], a);
    }

    for(int i=0; i<n; i++){
        if(add[i] != INF){
            ans+=add[i];
        }
    }

    return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '6', found: '4'
2 Halted 0 ms 0 KB -