oj.uz

Submission #1058906

# Submission time Handle Problem Language Result Execution time Memory
1058906 2024-08-14T14:58:16 Z shenfe1 Ancient Books (IOI17_books) C++17
42 / 100
 2000 ms 119816 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,bds;
    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()});
            int l=0,r=n-1;
            for(int f:vec){
                if(f<=s)l=f;
                else{
                    r=f;
                    break;
                }
            }
            bds.pb({l,r});
            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++){
        // if(pref[i]==0)cout<<i<<"\n";
        prefz[i]=prefz[i-1]+(pref[i]==0);
    }
    int cur=0;
    int L=s,R=s;
    while(R-L+1!=n){
        while(L-1>=0&&pref[L-1]!=0)L--;
        while(R+1<n&&pref[R]!=0)R++;
        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);
                    }
                }
            }
        }
        if(!ok){
            int mn=n+10,pos=-1;
            for(int i=0;i<sz(seg);i++){
                auto [l,r]=bds[i];
                if(l<=s&&s<=r&&i!=num[s]){
                    if(seg[i].F<L&&seg[i].S>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){
                // cout<<seg[pos].F<<" "<<seg[pos].S<<"\n";
                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]!=0)R++;
        // cout<<L<<" "<<R<<"\n";
        if(!ok){
            if(L-1>=0){
                L--;
                ans+=2;
            }
            if(R+1<n){
                R++;
                ans+=2;
            }
        }
    }
    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:107:9: warning: unused variable 'cur' [-Wunused-variable]
  107 |     int cur=0;
      |         ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30044 KB Output is correct
2 Correct 4 ms 30116 KB Output is correct
3 Correct 4 ms 29916 KB Output is correct
4 Correct 4 ms 29880 KB Output is correct
5 Correct 4 ms 30044 KB Output is correct
6 Correct 4 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 5 ms 30040 KB Output is correct
9 Correct 4 ms 30040 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 4 ms 29904 KB Output is correct
15 Correct 4 ms 30044 KB Output is correct
16 Correct 6 ms 30044 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 6 ms 30044 KB Output is correct
19 Correct 4 ms 30044 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30044 KB Output is correct
22 Correct 5 ms 30208 KB Output is correct
23 Correct 5 ms 30044 KB Output is correct
24 Correct 7 ms 30180 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 6 ms 30040 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 4 ms 30044 KB Output is correct
29 Correct 6 ms 30044 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30044 KB Output is correct
2 Correct 4 ms 30116 KB Output is correct
3 Correct 4 ms 29916 KB Output is correct
4 Correct 4 ms 29880 KB Output is correct
5 Correct 4 ms 30044 KB Output is correct
6 Correct 4 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 5 ms 30040 KB Output is correct
9 Correct 4 ms 30040 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 4 ms 29904 KB Output is correct
15 Correct 4 ms 30044 KB Output is correct
16 Correct 6 ms 30044 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 6 ms 30044 KB Output is correct
19 Correct 4 ms 30044 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30044 KB Output is correct
22 Correct 5 ms 30208 KB Output is correct
23 Correct 5 ms 30044 KB Output is correct
24 Correct 7 ms 30180 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 6 ms 30040 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 4 ms 30044 KB Output is correct
29 Correct 6 ms 30044 KB Output is correct
30 Correct 140 ms 57020 KB Output is correct
31 Correct 141 ms 55488 KB Output is correct
32 Execution timed out 2033 ms 119816 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30044 KB Output is correct
2 Correct 6 ms 30164 KB Output is correct
3 Correct 4 ms 30044 KB Output is correct
4 Correct 5 ms 30032 KB Output is correct
5 Correct 4 ms 30216 KB Output is correct
6 Correct 6 ms 30040 KB Output is correct
7 Correct 4 ms 30044 KB Output is correct
8 Correct 4 ms 30044 KB Output is correct
9 Correct 4 ms 30044 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct
11 Correct 7 ms 30160 KB Output is correct
12 Correct 5 ms 30192 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 5 ms 30144 KB Output is correct
15 Correct 4 ms 30044 KB Output is correct
16 Correct 6 ms 30044 KB Output is correct
17 Correct 7 ms 30144 KB Output is correct
18 Correct 4 ms 30044 KB Output is correct
19 Correct 4 ms 30044 KB Output is correct
20 Correct 6 ms 30044 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30044 KB Output is correct
2 Correct 4 ms 30116 KB Output is correct
3 Correct 4 ms 29916 KB Output is correct
4 Correct 4 ms 29880 KB Output is correct
5 Correct 4 ms 30044 KB Output is correct
6 Correct 4 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 5 ms 30040 KB Output is correct
9 Correct 4 ms 30040 KB Output is correct
10 Correct 4 ms 30044 KB Output is correct
11 Correct 4 ms 30044 KB Output is correct
12 Correct 6 ms 30044 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 4 ms 29904 KB Output is correct
15 Correct 4 ms 30044 KB Output is correct
16 Correct 6 ms 30044 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 6 ms 30044 KB Output is correct
19 Correct 4 ms 30044 KB Output is correct
20 Correct 4 ms 30044 KB Output is correct
21 Correct 6 ms 30044 KB Output is correct
22 Correct 5 ms 30208 KB Output is correct
23 Correct 5 ms 30044 KB Output is correct
24 Correct 7 ms 30180 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 6 ms 30040 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 4 ms 30044 KB Output is correct
29 Correct 6 ms 30044 KB Output is correct
30 Correct 140 ms 57020 KB Output is correct
31 Correct 141 ms 55488 KB Output is correct
32 Execution timed out 2033 ms 119816 KB Time limit exceeded
33 Halted 0 ms 0 KB -