oj.uz

Submission #1058698

# Submission time Handle Problem Language Result Execution time Memory
1058698 2024-08-14T12:25:31 Z shenfe1 Ancient Books (IOI17_books) C++17
22 / 100
 2000 ms 88928 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

const int MAX=1e6+10;

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

ll minimum_walk(vector<int> p,int s){
    n=sz(p);
    while(n>1&&p[n-1]==n-1)n--;
    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]){
                vec.pb(v);
                use[v]=1;
                v=p[v];
            }
            sort(all(vec));
            seg.pb({vec[0],vec.back()});
            x.pb(vec);
        }
    }
    int L,R;
    for(vector<int> v:x){
        for(int f:v){
            if(f==s){
                L=v[0],R=v.back();
            }
        }
    }
    while(R-L+1!=n){
        bool ok=0;
        for(int i=0;i<sz(seg);i++){
            auto [l,r]=seg[i];
            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){
            if(L-1>=0){
                L--;
                ans+=2;
            }
            if(R+1<n){
                R++;
                ans+=2;
            }
        }
    }

    return ans;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:55:12: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     while(R-L+1!=n){
      |           ~^~
books.cpp:55:12: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 3 ms 26560 KB Output is correct
3 Correct 3 ms 26460 KB Output is correct
4 Correct 4 ms 26460 KB Output is correct
5 Correct 4 ms 26460 KB Output is correct
6 Correct 4 ms 26560 KB Output is correct
7 Correct 3 ms 26588 KB Output is correct
8 Correct 4 ms 26460 KB Output is correct
9 Correct 4 ms 26592 KB Output is correct
10 Correct 4 ms 26712 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26592 KB Output is correct
13 Correct 3 ms 26460 KB Output is correct
14 Correct 3 ms 26544 KB Output is correct
15 Correct 3 ms 26460 KB Output is correct
16 Correct 3 ms 26460 KB Output is correct
17 Correct 3 ms 26584 KB Output is correct
18 Correct 3 ms 26576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 3 ms 26560 KB Output is correct
3 Correct 3 ms 26460 KB Output is correct
4 Correct 4 ms 26460 KB Output is correct
5 Correct 4 ms 26460 KB Output is correct
6 Correct 4 ms 26560 KB Output is correct
7 Correct 3 ms 26588 KB Output is correct
8 Correct 4 ms 26460 KB Output is correct
9 Correct 4 ms 26592 KB Output is correct
10 Correct 4 ms 26712 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26592 KB Output is correct
13 Correct 3 ms 26460 KB Output is correct
14 Correct 3 ms 26544 KB Output is correct
15 Correct 3 ms 26460 KB Output is correct
16 Correct 3 ms 26460 KB Output is correct
17 Correct 3 ms 26584 KB Output is correct
18 Correct 3 ms 26576 KB Output is correct
19 Correct 4 ms 26712 KB Output is correct
20 Correct 3 ms 26612 KB Output is correct
21 Correct 4 ms 26460 KB Output is correct
22 Correct 5 ms 26552 KB Output is correct
23 Correct 5 ms 26460 KB Output is correct
24 Correct 4 ms 26588 KB Output is correct
25 Correct 5 ms 26460 KB Output is correct
26 Correct 4 ms 26460 KB Output is correct
27 Correct 4 ms 26460 KB Output is correct
28 Correct 4 ms 26564 KB Output is correct
29 Correct 4 ms 26460 KB Output is correct

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 3 ms 26560 KB Output is correct
3 Correct 3 ms 26460 KB Output is correct
4 Correct 4 ms 26460 KB Output is correct
5 Correct 4 ms 26460 KB Output is correct
6 Correct 4 ms 26560 KB Output is correct
7 Correct 3 ms 26588 KB Output is correct
8 Correct 4 ms 26460 KB Output is correct
9 Correct 4 ms 26592 KB Output is correct
10 Correct 4 ms 26712 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26592 KB Output is correct
13 Correct 3 ms 26460 KB Output is correct
14 Correct 3 ms 26544 KB Output is correct
15 Correct 3 ms 26460 KB Output is correct
16 Correct 3 ms 26460 KB Output is correct
17 Correct 3 ms 26584 KB Output is correct
18 Correct 3 ms 26576 KB Output is correct
19 Correct 4 ms 26712 KB Output is correct
20 Correct 3 ms 26612 KB Output is correct
21 Correct 4 ms 26460 KB Output is correct
22 Correct 5 ms 26552 KB Output is correct
23 Correct 5 ms 26460 KB Output is correct
24 Correct 4 ms 26588 KB Output is correct
25 Correct 5 ms 26460 KB Output is correct
26 Correct 4 ms 26460 KB Output is correct
27 Correct 4 ms 26460 KB Output is correct
28 Correct 4 ms 26564 KB Output is correct
29 Correct 4 ms 26460 KB Output is correct
30 Correct 142 ms 50940 KB Output is correct
31 Correct 132 ms 47812 KB Output is correct
32 Correct 58 ms 40980 KB Output is correct
33 Execution timed out 2021 ms 88928 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26460 KB Output is correct
2 Correct 3 ms 26560 KB Output is correct
3 Correct 3 ms 26460 KB Output is correct
4 Correct 4 ms 26460 KB Output is correct
5 Correct 4 ms 26460 KB Output is correct
6 Correct 4 ms 26560 KB Output is correct
7 Correct 3 ms 26588 KB Output is correct
8 Correct 4 ms 26460 KB Output is correct
9 Correct 4 ms 26592 KB Output is correct
10 Correct 4 ms 26712 KB Output is correct
11 Correct 4 ms 26460 KB Output is correct
12 Correct 4 ms 26592 KB Output is correct
13 Correct 3 ms 26460 KB Output is correct
14 Correct 3 ms 26544 KB Output is correct
15 Correct 3 ms 26460 KB Output is correct
16 Correct 3 ms 26460 KB Output is correct
17 Correct 3 ms 26584 KB Output is correct
18 Correct 3 ms 26576 KB Output is correct
19 Correct 4 ms 26712 KB Output is correct
20 Correct 3 ms 26612 KB Output is correct
21 Correct 4 ms 26460 KB Output is correct
22 Correct 5 ms 26552 KB Output is correct
23 Correct 5 ms 26460 KB Output is correct
24 Correct 4 ms 26588 KB Output is correct
25 Correct 5 ms 26460 KB Output is correct
26 Correct 4 ms 26460 KB Output is correct
27 Correct 4 ms 26460 KB Output is correct
28 Correct 4 ms 26564 KB Output is correct
29 Correct 4 ms 26460 KB Output is correct
30 Correct 142 ms 50940 KB Output is correct
31 Correct 132 ms 47812 KB Output is correct
32 Correct 58 ms 40980 KB Output is correct
33 Execution timed out 2021 ms 88928 KB Time limit exceeded
34 Halted 0 ms 0 KB -