Submission #565278

#	Time	Username	Problem	Language	Result	Execution time	Memory
565278		hoanghq2004	Ancient Books (IOI17_books)	C++14	0 / 100	1 ms	340 KiB

books

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "books.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

long long minimum_walk(vector<int> p, int s) {
    int n = p.size();
    vector <int> vis(n, 0);
    vector <pair <int, int>> S;
    long long tot = 0;
    for (int u = 0; u < n; ++u) {
        tot += abs(u - p[u]);
        if (vis[u]) continue;
        int v = u;
        int mini = 1e9, maxi = - 1e9;
        do {
            mini = min(mini, v);
            maxi = max(maxi, v);
            v = p[v];
            vis[v] = 1;
        } while (u != v);
        S.push_back({mini, -1});
        S.push_back({maxi, 1});
    }
    sort(S.begin(), S.end());
    int cur = 0;
    int E = 0;
    for (auto [x, sign]: S) {
        cur -= sign;
        if (cur == 0) ++E;
    }
//    cout << tot << '\n';
    --E;
    return tot + E * 2;
}

//
//int main() {
//	int n, s;
//	assert(2 == scanf("%d %d", &n, &s));
//
//	vector<int> p((unsigned) n);
//	for(int i = 0; i < n; i++)
//		assert(1 == scanf("%d", &p[(unsigned) i]));
//
//	long long res = minimum_walk(p, s);
//	printf("%lld\n", res);
//
//	return 0;
//}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [x, sign]: S) {
      |               ^

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