제출 #1061811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061811		_8_8_	고대 책들 (IOI17_books)	C++17	50 / 100	70 ms	8248 KiB

books

#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 {
            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--;
                }
                if(r < tr) {
                    res += 2;
                    r++;
                }
            } else {
                if(l <= tl) {
                    res += 2;
                    r++;
                } else if(r >= tr) {
                    res += 2;
                    l--;
                } else {
                    if(l - l_ <= r_ - r) {
                        res += 2;
                        l--;
                    } else {
                        res += 2;
                        r++;
                    }
                }
            }
        }
    }
    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

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:87:17: warning: 'tl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |                 if(l <= tl) {
      |                 ^~
books.cpp:17:13: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |         int nn;
      |             ^~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30