oj.uz

Submission #1058899

# Submission time Handle Problem Language Result Execution time Memory
1058899 2024-08-14T14:54:24 Z shenfe1 Ancient Books (IOI17_books) C++17
22 / 100
 2000 ms 115788 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]){
            // cout<<l<<" "<<r<<"\n";
            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){
        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]=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]!=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:98:9: warning: unused variable 'cur' [-Wunused-variable]
   98 |     int cur=0;
      |         ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30044 KB Output is correct
2 Correct 4 ms 29904 KB Output is correct
3 Correct 4 ms 30040 KB Output is correct
4 Correct 4 ms 30012 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 4 ms 30044 KB Output is correct
7 Correct 5 ms 30044 KB Output is correct
8 Correct 4 ms 30100 KB Output is correct
9 Correct 4 ms 30116 KB Output is correct
10 Correct 4 ms 30040 KB Output is correct
11 Correct 4 ms 30104 KB Output is correct
12 Correct 6 ms 29908 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 4 ms 30044 KB Output is correct
15 Correct 6 ms 29888 KB Output is correct
16 Correct 4 ms 30044 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 5 ms 30040 KB Output is correct
19 Correct 4 ms 29900 KB Output is correct
20 Correct 6 ms 30044 KB Output is correct
21 Correct 5 ms 30208 KB Output is correct
22 Correct 7 ms 30112 KB Output is correct
23 Correct 5 ms 30204 KB Output is correct
24 Correct 4 ms 30100 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 4 ms 30116 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 4 ms 30044 KB Output is correct
29 Correct 4 ms 30116 KB Output is correct
30 Correct 143 ms 60860 KB Output is correct
31 Correct 183 ms 59216 KB Output is correct
32 Execution timed out 2024 ms 115788 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 30044 KB Output is correct
2 Correct 4 ms 29904 KB Output is correct
3 Correct 4 ms 30040 KB Output is correct
4 Correct 4 ms 30012 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 4 ms 30044 KB Output is correct
7 Correct 5 ms 30044 KB Output is correct
8 Correct 4 ms 30100 KB Output is correct
9 Correct 4 ms 30116 KB Output is correct
10 Correct 4 ms 30040 KB Output is correct
11 Correct 4 ms 30104 KB Output is correct
12 Correct 6 ms 29908 KB Output is correct
13 Correct 4 ms 30044 KB Output is correct
14 Correct 4 ms 30044 KB Output is correct
15 Correct 6 ms 29888 KB Output is correct
16 Correct 4 ms 30044 KB Output is correct
17 Correct 6 ms 30044 KB Output is correct
18 Correct 5 ms 30040 KB Output is correct
19 Correct 4 ms 29900 KB Output is correct
20 Correct 6 ms 30044 KB Output is correct
21 Correct 5 ms 30208 KB Output is correct
22 Correct 7 ms 30112 KB Output is correct
23 Correct 5 ms 30204 KB Output is correct
24 Correct 4 ms 30100 KB Output is correct
25 Correct 4 ms 30044 KB Output is correct
26 Correct 4 ms 30116 KB Output is correct
27 Correct 4 ms 30044 KB Output is correct
28 Correct 4 ms 30044 KB Output is correct
29 Correct 4 ms 30116 KB Output is correct
30 Correct 143 ms 60860 KB Output is correct
31 Correct 183 ms 59216 KB Output is correct
32 Execution timed out 2024 ms 115788 KB Time limit exceeded
33 Halted 0 ms 0 KB -