oj.uz

Submission #1061806

# Submission time Handle Problem Language Result Execution time Memory
1061806 2024-08-16T13:41:45 Z _8_8_ Ancient Books (IOI17_books) C++17
12 / 100
 1 ms 600 KB 
#include "books.h"
#include <bits/stdc++.h>
    
using namespace std;
typedef long long ll;
const int N = 1e6 + 12;
int n;

long long minimum_walk(vector<int> p, int s) {
    n = (int)p.size();
    int it = 0;
    ll res = 0;
    for(int i = 0;i < n;i++) {
        res += abs(i - p[i]);
    }
    // if(s == 0) {
    //     int nn;
    //     for(int i = n - 1;i >= 0;i--) {
    //         if(p[i] != i) {
    //             nn = i;
    //             break;
    //         }
    //     }
    //     int mx = -1;
    //     for(int i = 0;i < nn;i++) {
    //         mx = max(mx,p[i]);
    //         if(mx == i) {
    //             res += 2;
    //         }
    //     }
    //     return res;
    // }
    

    int l = s,r = s,R = s,L = s;
    int tl,tr;
    for(int i = 0;i < n;i++) {
        if(p[i] != i) {
            tl = i;
            break;
        }
    }
    for(int i = n - 1;i >= 0;i--) {
        if(i != p[i]) {
            tr = i;
            break;
        }
    }
    if(!res) {
        return res;
    }
    while(true) {
        R = max({R,p[r],p[l]});
        L = min({L,p[l],p[r]});
        if(l <= tl && r >= tr) {
            break;
        }
        if(r < R && tr >r) {
            r++;
        } else if(L < l && l >tl) {
            l--;
        } else {
            r++;
            int l_ = -1e9,r_ = (int)1e9;
            for(int i = l - 1;i >= tl;i--) {
                if(p[i] > r) {
                    l_ = i;
                    break;
                }
            }
            for(int i = r + 1;i <= tr;i++) {
                if(p[i] < l) {
                    r_ = i;
                    break;
                }
            }
            if(l_ == (int)-1e9 && r_ == (int)1e9) {
                if(l > tl) {
                    res += 2;
                    l--;
                }
                if(r < tr) {
                    res += 2;
                    r++;
                }
            } else {
                if(l <= tl || l_ == (int)-1e9) {
                    res += 2;
                    r++;
                } else if(r >= tr || r_ == (int)1e9) {
                    res += 2;
                    l--;
                } else {
                    if(l - l_ < r_ - r) {
                        res += 2;
                        l--;
                    } else {
                        res += 2;
                        r++;
                    }
                }
            }
        }
    }
    return res;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:11:9: warning: unused variable 'it' [-Wunused-variable]
   11 |     int it = 0;
      |         ^~
books.cpp:36:12: warning: 'tr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     int tl,tr;
      |            ^~
books.cpp:36:9: warning: 'tl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     int tl,tr;
      |         ^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1590'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1590'
23 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '2094', found: '1470'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1590'
23 Halted 0 ms 0 KB -