oj.uz

Submission #1058867

# Submission time Handle Problem Language Result Execution time Memory
1058867 2024-08-14T14:38:42 Z shenfe1 Ancient Books (IOI17_books) C++17
22 / 100
 2000 ms 118528 KB 
#include <bits/stdc++.h>
#include "books.h"

#pragma GCC optimize("Ofast")

using namespace std;

#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ll long long
#define lb lower_bound

const int MAX=1e6+10;
const ll inf=1e18;

int n;
vector<int> g[MAX];
bool use[MAX];
vector<int> vec;
int pref[MAX];

struct dsu{
    int f[MAX];

    void init(int n){
        for(int i=0;i<n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }

    void unite(int a,int b){
        a=get(a),b=get(b);
        f[a]=b;
    }
}d;

int num[MAX];
int prefz[MAX];

bool is(int l,int r,vector<int> x){
    for(int pos:x){
        if(l<=pos&&pos<=r)return 1;
    }
    return 0;
}

int get(int l,int r){
    if(l==0)return prefz[r];
    return prefz[r]-prefz[l-1];
}

ll minimum_walk(vector<int> p,int s){
    n=sz(p);
    int Lneed=0,Rneed=n-1;
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=abs(i-p[i]);
    }
    vector<vector<int>> x;
    vector<pii> seg;
    for(int i=0;i<n;i++){
        if(!use[i]){
            vec.clear();
            int v=i;
            while(!use[v]){
                num[v]=sz(seg);
                vec.pb(v);
                use[v]=1;
                v=p[v];
            }
            sort(all(vec));
            seg.pb({vec[0],vec.back()});
            x.pb(vec);
        }
    }
    d.init(n);
    vector<int> pref(n,0);
    for(int i=0;i<sz(seg);i++){
        auto &[l,r]=seg[i];
        if(l<=s&&s<=r&&i!=num[s])continue;
        pref[l]++;
        pref[r]--;
    }
    for(int i=1;i<n;i++)pref[i]+=pref[i-1];
    prefz[0]=(pref[0]==0);
    for(int i=1;i<n;i++){
        prefz[i]=prefz[i-1]+(pref[i]==0);
    }
    int cur=0;
    int L=s,R=s;
    while(R-L+1!=n){
        bool ok=0;
        for(int i=0;i<sz(seg);i++){
            auto [l,r]=seg[i];
            if(l<=s&&s<=r&&i!=num[s]){
                for(int pos:x[i]){
                    if(l<=pos&&pos<=r){
                        if(l<L||r>R)ok=1;
                        L=min(L,l);
                        R=max(R,r);
                    }
                }
            }
        }
        // cout<<L<<" "<<R<<"\n";
        if(!ok){
            int mn=n+10,pos=-1;
            for(int i=0;i<sz(seg);i++){
                auto [l,r]=seg[i];
                if(l<=s&&s<=r&&i!=num[s]){
                    if(l<L&&r>R){
                        if(get(l,L-1)<mn){
                            mn=get(l,L-1);
                            pos=i;
                        }
                        if(get(R,r-1)<mn){
                            mn=get(R,r-1);
                            pos=i;
                        }
                    }
                }
            }
            if(pos!=-1){
                ok=1;
                ans+=2*mn;
                L=seg[pos].F,R=seg[pos].S;
            }
        }
        while(L-1>=0&&pref[L-1]!=0)L--;
        while(R+1<n&&pref[R])R++;
        if(!ok){
            if(L-1>=0){
                L--;
                ans+=2;
            }
            if(R+1<n){
                R++;
                ans+=2;
            }
        }
    }
    // cout<<ans<<"\n";
    for(int i=0;i<s;i++){
        if(p[i]==i)ans-=2;
        else break;
    }
    for(int i=n-1;i>s;i--){
        if(p[i]==i)ans-=2;
        else break;
    }

    return ans;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:60:9: warning: unused variable 'Lneed' [-Wunused-variable]
   60 |     int Lneed=0,Rneed=n-1;
      |         ^~~~~
books.cpp:60:17: warning: unused variable 'Rneed' [-Wunused-variable]
   60 |     int Lneed=0,Rneed=n-1;
      |                 ^~~~~
books.cpp:95:9: warning: unused variable 'cur' [-Wunused-variable]
   95 |     int cur=0;
      |         ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30040 KB Output is correct
2 Correct 4 ms 30044 KB Output is correct
3 Correct 4 ms 30044 KB Output is correct
4 Correct 4 ms 30044 KB Output is correct
5 Correct 4 ms 30124 KB Output is correct
6 Correct 4 ms 29908 KB Output is correct
7 Correct 4 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 5 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 5 ms 30080 KB Output is correct
17 Correct 4 ms 30044 KB Output is correct
18 Correct 4 ms 30104 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30040 KB Output is correct
2 Correct 4 ms 30044 KB Output is correct
3 Correct 4 ms 30044 KB Output is correct
4 Correct 4 ms 30044 KB Output is correct
5 Correct 4 ms 30124 KB Output is correct
6 Correct 4 ms 29908 KB Output is correct
7 Correct 4 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 5 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 5 ms 30080 KB Output is correct
17 Correct 4 ms 30044 KB Output is correct
18 Correct 4 ms 30104 KB Output is correct
19 Correct 4 ms 30040 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30136 KB Output is correct
22 Correct 8 ms 30044 KB Output is correct
23 Correct 7 ms 30044 KB Output is correct
24 Correct 4 ms 30124 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 4 ms 30160 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 6 ms 30044 KB Output is correct
29 Correct 4 ms 30044 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30040 KB Output is correct
2 Correct 4 ms 30044 KB Output is correct
3 Correct 4 ms 30044 KB Output is correct
4 Correct 4 ms 30044 KB Output is correct
5 Correct 4 ms 30124 KB Output is correct
6 Correct 4 ms 29908 KB Output is correct
7 Correct 4 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 5 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 5 ms 30080 KB Output is correct
17 Correct 4 ms 30044 KB Output is correct
18 Correct 4 ms 30104 KB Output is correct
19 Correct 4 ms 30040 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30136 KB Output is correct
22 Correct 8 ms 30044 KB Output is correct
23 Correct 7 ms 30044 KB Output is correct
24 Correct 4 ms 30124 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 4 ms 30160 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 6 ms 30044 KB Output is correct
29 Correct 4 ms 30044 KB Output is correct
30 Correct 165 ms 63416 KB Output is correct
31 Correct 141 ms 61892 KB Output is correct
32 Execution timed out 2091 ms 118528 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30040 KB Output is correct
2 Correct 4 ms 30044 KB Output is correct
3 Correct 4 ms 30044 KB Output is correct
4 Correct 4 ms 30044 KB Output is correct
5 Correct 4 ms 30124 KB Output is correct
6 Correct 4 ms 29908 KB Output is correct
7 Correct 4 ms 30044 KB Output is correct
8 Correct 6 ms 30044 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 5 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 6 ms 30044 KB Output is correct
15 Correct 6 ms 30044 KB Output is correct
16 Correct 5 ms 30080 KB Output is correct
17 Correct 4 ms 30044 KB Output is correct
18 Correct 4 ms 30104 KB Output is correct
19 Correct 4 ms 30040 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30136 KB Output is correct
22 Correct 8 ms 30044 KB Output is correct
23 Correct 7 ms 30044 KB Output is correct
24 Correct 4 ms 30124 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 4 ms 30160 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 6 ms 30044 KB Output is correct
29 Correct 4 ms 30044 KB Output is correct
30 Correct 165 ms 63416 KB Output is correct
31 Correct 141 ms 61892 KB Output is correct
32 Execution timed out 2091 ms 118528 KB Time limit exceeded
33 Halted 0 ms 0 KB -