oj.uz

Submission #1061820

# Submission time Handle Problem Language Result Execution time Memory
1061820 2024-08-16T13:59:38 Z _8_8_ Ancient Books (IOI17_books) C++17
0 / 100
 0 ms 348 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 = -1;
    //     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 {
            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) {
                assert(r_ == (int)1e9);
                if(l > tl) {
                    res += 2;
                    l--;
                    int mn = (int)1e9;
                    for(int j = l;j >= tl;--j) {
                        assert(p[j] <= l && p[j] >= tl);
                        mn = min(mn,p[j]);
                        if(j == mn) {
                            res += 2;
                        }
                    }
                }
                if(r < tr) {
                    res += 2;
                    r++;
                    int mx = -1;
                    for(int j = r;j <= tr;j++) {
                        assert(p[j] >= r && p[j] <= tr);
                        mx = max(mx,p[j]);
                        if(mx == j) {
                            res += 2;
                        }
                    }
                }
                return res;
            } 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
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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