Submission #1061736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061736		_8_8_	Ancient Books (IOI17_books)	C++17	50 / 100	170 ms	21204 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]);
    }
    for(int i = 0;i < n;i++) {
        if(c[i]) continue;
        it++;
        vector<int> v;
        int x = i;
        while(c[x] != it) {
            c[x] = it;
            x = p[x];
            v.push_back(x);
        }
        sort(v.begin(),v.end());
        isl[v[0]] = isr[v.back()] = 1;
    }
    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;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:30:9: warning: 'nn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     int nn;
      |         ^~

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