제출 #1061807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061807		_8_8_	고대 책들 (IOI17_books)	C++17	22 / 100	2065 ms	8176 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 && 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;
}

컴파일 시 표준 에러 (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:36:9: warning: 'tl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     int tl,tr;
      |         ^~

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