Submission #1061792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061792		_8_8_	Ancient Books (IOI17_books)	C++17	50 / 100	79 ms	13068 KiB

books

#include "books.h"
#include <bits/stdc++.h>
    
using namespace std;
typedef long long ll;
const int N = 1e6 + 12;
int n;
int c[N];
bool isl[N],isr[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++;
            res += 2;
        }
    }
    return res;
}

Compilation message (stderr)

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

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