# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40161 | 2018-01-28T19:54:08 Z | alenam0161 | Ancient Books (IOI17_books) | C++14 | 0 ms | 3976 KB |
#include "books.h" #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 7; bool used[N]; vector<int> cycl,a; long long ans; void dfs(int v) { used[v] = true; cycl.push_back(v); ans += abs(a[v] - v); if (used[a[v]])return; dfs(a[v]); } void print(vector<int> v) { for (int to : v) { cout << to << " :"; } cout << endl; } bool us[N]; long long minimum_walk(std::vector<int> p, int s) { a = p; int n = p.size(); vector<pair<long long,int>> ms; vector<pair<int,int>> art; int lst = n - 1; while (lst >= 0 && p[lst] == lst)lst--; for (int i = 0; i < n; ++i) { if (used[i])continue; ans = 0; cycl.clear(); dfs(i); if (ans > 0) { ms.push_back({ ans,i }); sort(cycl.begin(), cycl.end()); art.push_back({ cycl[0],cycl.back() }); } } while (ms.size() > 0 && ms.back().first == 0)ms.pop_back(); if (ms.size() == 0)return 0ll; long long an = 0; for (int i = 0; i < ms.size(); ++i) { an += ms[i].first;// cout << ms[i].first << " " << ms[i].second << endl; } an += ms.back().second * 2ll; for (int i = 0; i < art.size(); ++i) { int q = 0; for (int j = 0; j < art.size(); ++j) { if (i == j)continue; if (art[j].first >= art[i].first&&art[i].second >= art[j].second) an -= (art[j].first - art[i].first) * 2; } } return an; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3976 KB | Output is correct |
2 | Correct | 0 ms | 3976 KB | Output is correct |
3 | Correct | 0 ms | 3976 KB | Output is correct |
4 | Correct | 0 ms | 3976 KB | Output is correct |
5 | Correct | 0 ms | 3976 KB | Output is correct |
6 | Correct | 0 ms | 3976 KB | Output is correct |
7 | Correct | 0 ms | 3976 KB | Output is correct |
8 | Correct | 0 ms | 3976 KB | Output is correct |
9 | Correct | 0 ms | 3976 KB | Output is correct |
10 | Correct | 0 ms | 3976 KB | Output is correct |
11 | Correct | 0 ms | 3976 KB | Output is correct |
12 | Correct | 0 ms | 3976 KB | Output is correct |
13 | Correct | 0 ms | 3976 KB | Output is correct |
14 | Correct | 0 ms | 3976 KB | Output is correct |
15 | Correct | 0 ms | 3976 KB | Output is correct |
16 | Correct | 0 ms | 3976 KB | Output is correct |
17 | Correct | 0 ms | 3976 KB | Output is correct |
18 | Correct | 0 ms | 3976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3976 KB | Output is correct |
2 | Correct | 0 ms | 3976 KB | Output is correct |
3 | Correct | 0 ms | 3976 KB | Output is correct |
4 | Correct | 0 ms | 3976 KB | Output is correct |
5 | Correct | 0 ms | 3976 KB | Output is correct |
6 | Correct | 0 ms | 3976 KB | Output is correct |
7 | Correct | 0 ms | 3976 KB | Output is correct |
8 | Correct | 0 ms | 3976 KB | Output is correct |
9 | Correct | 0 ms | 3976 KB | Output is correct |
10 | Correct | 0 ms | 3976 KB | Output is correct |
11 | Correct | 0 ms | 3976 KB | Output is correct |
12 | Correct | 0 ms | 3976 KB | Output is correct |
13 | Correct | 0 ms | 3976 KB | Output is correct |
14 | Correct | 0 ms | 3976 KB | Output is correct |
15 | Correct | 0 ms | 3976 KB | Output is correct |
16 | Correct | 0 ms | 3976 KB | Output is correct |
17 | Correct | 0 ms | 3976 KB | Output is correct |
18 | Correct | 0 ms | 3976 KB | Output is correct |
19 | Incorrect | 0 ms | 3976 KB | 3rd lines differ - on the 1st token, expected: '338572', found: '336240' |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3976 KB | Output is correct |
2 | Correct | 0 ms | 3976 KB | Output is correct |
3 | Correct | 0 ms | 3976 KB | Output is correct |
4 | Correct | 0 ms | 3976 KB | Output is correct |
5 | Correct | 0 ms | 3976 KB | Output is correct |
6 | Correct | 0 ms | 3976 KB | Output is correct |
7 | Correct | 0 ms | 3976 KB | Output is correct |
8 | Correct | 0 ms | 3976 KB | Output is correct |
9 | Correct | 0 ms | 3976 KB | Output is correct |
10 | Correct | 0 ms | 3976 KB | Output is correct |
11 | Correct | 0 ms | 3976 KB | Output is correct |
12 | Correct | 0 ms | 3976 KB | Output is correct |
13 | Correct | 0 ms | 3976 KB | Output is correct |
14 | Correct | 0 ms | 3976 KB | Output is correct |
15 | Correct | 0 ms | 3976 KB | Output is correct |
16 | Correct | 0 ms | 3976 KB | Output is correct |
17 | Correct | 0 ms | 3976 KB | Output is correct |
18 | Correct | 0 ms | 3976 KB | Output is correct |
19 | Incorrect | 0 ms | 3976 KB | 3rd lines differ - on the 1st token, expected: '338572', found: '336240' |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 3976 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '-170336' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 3976 KB | Output is correct |
2 | Correct | 0 ms | 3976 KB | Output is correct |
3 | Correct | 0 ms | 3976 KB | Output is correct |
4 | Correct | 0 ms | 3976 KB | Output is correct |
5 | Correct | 0 ms | 3976 KB | Output is correct |
6 | Correct | 0 ms | 3976 KB | Output is correct |
7 | Correct | 0 ms | 3976 KB | Output is correct |
8 | Correct | 0 ms | 3976 KB | Output is correct |
9 | Correct | 0 ms | 3976 KB | Output is correct |
10 | Correct | 0 ms | 3976 KB | Output is correct |
11 | Correct | 0 ms | 3976 KB | Output is correct |
12 | Correct | 0 ms | 3976 KB | Output is correct |
13 | Correct | 0 ms | 3976 KB | Output is correct |
14 | Correct | 0 ms | 3976 KB | Output is correct |
15 | Correct | 0 ms | 3976 KB | Output is correct |
16 | Correct | 0 ms | 3976 KB | Output is correct |
17 | Correct | 0 ms | 3976 KB | Output is correct |
18 | Correct | 0 ms | 3976 KB | Output is correct |
19 | Incorrect | 0 ms | 3976 KB | 3rd lines differ - on the 1st token, expected: '338572', found: '336240' |
20 | Halted | 0 ms | 0 KB | - |