oj.uz

Submission #565285

# Submission time Handle Problem Language Result Execution time Memory
565285 2022-05-20T15:26:51 Z hoanghq2004 Ancient Books (IOI17_books) C++14
0 / 100
 1 ms 340 KB 
#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;
    int last = n;
    for (int i = n - 1; i >= 0; --i) {
        if (p[i] != i) {
            last = i + 1;
            break;
        }
    }
    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);
            vis[v] = 1;
            v = p[v];
        } 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) {
        if (x >= last) break;
        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

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

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 300 KB 3rd lines differ - on the 1st token, expected: '0', found: '6'
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 300 KB 3rd lines differ - on the 1st token, expected: '0', found: '6'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 300 KB 3rd lines differ - on the 1st token, expected: '0', found: '6'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 300 KB 3rd lines differ - on the 1st token, expected: '0', found: '6'
10 Halted 0 ms 0 KB -