Submission #1065745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065745		TheQuantiX	Ancient Books (IOI17_books)	C++17	50 / 100	609 ms	42756 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#pragma GCC optimize("O3,unroll-loops")

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000000000000LL;

ll n, m, q, k, x, y, a, b, c;

// map< pair< vector<int>, pair<int, int> >, ll > mp;
vector<int> perfect;

long long minimum_walk(vector<int> p, int s) {
    perfect.reserve(p.size());
    for (int i = 0; i < p.size(); i++) {
        perfect.push_back(i);
    }
    if (p == perfect) {
        return 0;
    }
    ll num = 0;
    set<int> st;
    vector<bool> b(p.size());
    for (int i = 0; i < p.size(); i++) {
        num += abs(i - p[i]);
        st.insert(p[i]);
        if (st.count(i)) {
            st.erase(i);
        }
        if (st.size() == 0 || *st.rbegin() <= i) {
            // cout << i << '\n';
            b[i] = 1;
        }
    }
    // cout << "DEBUG" << endl;
    bool fl = 0;
    for (int i = p.size() - 1; i >= 0; i--) {
        if (fl && b[i]) {
            num += 2;
        }
        if (p[i] != i) {
            fl = 1;
        }
    }
    return num;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~
books.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~

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