| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 70450 | 2018-08-22T22:58:16 Z | bnahmad15 | Ancient Books (IOI17_books) | C++17 | 2000 ms | 21328 KB |
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n;
bool vis[N];
vector<pair<vector<int>,long long> > v;
vector<int> points;
long long minimum_walk(std::vector<int> p, int s) {
n = p.size();
// do{
for(int i = 0;i<n;i++)
vis[i] = 0;
v.clear();
points.clear();
for(int i = 0;i<n;i++){
if(p[i] != i && vis[i] == false){
v.push_back(make_pair(vector<int>(),0));
v.back().first.push_back(i);
vis[i] = true;
v.back().second += 1LL * abs(p[i] - i);
int j = p[i];
while (j != i){
vis[j] = true;
v.back().first.push_back(j);
v.back().second += 1LL * abs(p[j] - j);
j = p[j];
}
}
}
long long res = 0;
if(v.size()){
// res = 2 * v[0].first[0];
points.push_back(0);
for(int i = 0;i<v.size();i++){
res += 1LL * v[i].second;
long long mn = -1;
for(int j = 0;j<v[i].first.size();j++){
for(int k = 0;k<points.size();k++){
if(mn == -1)
mn = 1LL * abs(points[k] - v[i].first[j]);
mn = min(mn,1LL * abs(points[k] - v[i].first[j]));
}
}
if(v[i].first[0] > points.back())
res += 2 * mn;
for(int j = 0;j<v[i].first.size();j++)
points.push_back(v[i].first[j]);
sort(points.begin(),points.end());
}
}
/* for(int i = 0;i<4;i++)
cout<<p[i]<<" ";
cout<<res<<endl;*/
// }while(next_permutation(p.begin(),p.end()));
return res;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 248 KB | Output is correct |
| 2 | Correct | 2 ms | 356 KB | Output is correct |
| 3 | Correct | 2 ms | 520 KB | Output is correct |
| 4 | Correct | 2 ms | 520 KB | Output is correct |
| 5 | Correct | 3 ms | 520 KB | Output is correct |
| 6 | Correct | 3 ms | 520 KB | Output is correct |
| 7 | Correct | 2 ms | 520 KB | Output is correct |
| 8 | Correct | 2 ms | 552 KB | Output is correct |
| 9 | Correct | 2 ms | 684 KB | Output is correct |
| 10 | Correct | 3 ms | 684 KB | Output is correct |
| 11 | Correct | 2 ms | 684 KB | Output is correct |
| 12 | Correct | 2 ms | 684 KB | Output is correct |
| 13 | Correct | 3 ms | 684 KB | Output is correct |
| 14 | Correct | 4 ms | 684 KB | Output is correct |
| 15 | Correct | 3 ms | 684 KB | Output is correct |
| 16 | Correct | 3 ms | 684 KB | Output is correct |
| 17 | Correct | 2 ms | 684 KB | Output is correct |
| 18 | Correct | 2 ms | 684 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 248 KB | Output is correct |
| 2 | Correct | 2 ms | 356 KB | Output is correct |
| 3 | Correct | 2 ms | 520 KB | Output is correct |
| 4 | Correct | 2 ms | 520 KB | Output is correct |
| 5 | Correct | 3 ms | 520 KB | Output is correct |
| 6 | Correct | 3 ms | 520 KB | Output is correct |
| 7 | Correct | 2 ms | 520 KB | Output is correct |
| 8 | Correct | 2 ms | 552 KB | Output is correct |
| 9 | Correct | 2 ms | 684 KB | Output is correct |
| 10 | Correct | 3 ms | 684 KB | Output is correct |
| 11 | Correct | 2 ms | 684 KB | Output is correct |
| 12 | Correct | 2 ms | 684 KB | Output is correct |
| 13 | Correct | 3 ms | 684 KB | Output is correct |
| 14 | Correct | 4 ms | 684 KB | Output is correct |
| 15 | Correct | 3 ms | 684 KB | Output is correct |
| 16 | Correct | 3 ms | 684 KB | Output is correct |
| 17 | Correct | 2 ms | 684 KB | Output is correct |
| 18 | Correct | 2 ms | 684 KB | Output is correct |
| 19 | Correct | 4 ms | 684 KB | Output is correct |
| 20 | Correct | 3 ms | 684 KB | Output is correct |
| 21 | Correct | 2 ms | 684 KB | Output is correct |
| 22 | Correct | 4 ms | 684 KB | Output is correct |
| 23 | Correct | 4 ms | 788 KB | Output is correct |
| 24 | Correct | 5 ms | 788 KB | Output is correct |
| 25 | Correct | 4 ms | 788 KB | Output is correct |
| 26 | Correct | 5 ms | 788 KB | Output is correct |
| 27 | Correct | 4 ms | 788 KB | Output is correct |
| 28 | Correct | 4 ms | 788 KB | Output is correct |
| 29 | Correct | 4 ms | 788 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 248 KB | Output is correct |
| 2 | Correct | 2 ms | 356 KB | Output is correct |
| 3 | Correct | 2 ms | 520 KB | Output is correct |
| 4 | Correct | 2 ms | 520 KB | Output is correct |
| 5 | Correct | 3 ms | 520 KB | Output is correct |
| 6 | Correct | 3 ms | 520 KB | Output is correct |
| 7 | Correct | 2 ms | 520 KB | Output is correct |
| 8 | Correct | 2 ms | 552 KB | Output is correct |
| 9 | Correct | 2 ms | 684 KB | Output is correct |
| 10 | Correct | 3 ms | 684 KB | Output is correct |
| 11 | Correct | 2 ms | 684 KB | Output is correct |
| 12 | Correct | 2 ms | 684 KB | Output is correct |
| 13 | Correct | 3 ms | 684 KB | Output is correct |
| 14 | Correct | 4 ms | 684 KB | Output is correct |
| 15 | Correct | 3 ms | 684 KB | Output is correct |
| 16 | Correct | 3 ms | 684 KB | Output is correct |
| 17 | Correct | 2 ms | 684 KB | Output is correct |
| 18 | Correct | 2 ms | 684 KB | Output is correct |
| 19 | Correct | 4 ms | 684 KB | Output is correct |
| 20 | Correct | 3 ms | 684 KB | Output is correct |
| 21 | Correct | 2 ms | 684 KB | Output is correct |
| 22 | Correct | 4 ms | 684 KB | Output is correct |
| 23 | Correct | 4 ms | 788 KB | Output is correct |
| 24 | Correct | 5 ms | 788 KB | Output is correct |
| 25 | Correct | 4 ms | 788 KB | Output is correct |
| 26 | Correct | 5 ms | 788 KB | Output is correct |
| 27 | Correct | 4 ms | 788 KB | Output is correct |
| 28 | Correct | 4 ms | 788 KB | Output is correct |
| 29 | Correct | 4 ms | 788 KB | Output is correct |
| 30 | Execution timed out | 2057 ms | 21328 KB | Time limit exceeded |
| 31 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 21328 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 248 KB | Output is correct |
| 2 | Correct | 2 ms | 356 KB | Output is correct |
| 3 | Correct | 2 ms | 520 KB | Output is correct |
| 4 | Correct | 2 ms | 520 KB | Output is correct |
| 5 | Correct | 3 ms | 520 KB | Output is correct |
| 6 | Correct | 3 ms | 520 KB | Output is correct |
| 7 | Correct | 2 ms | 520 KB | Output is correct |
| 8 | Correct | 2 ms | 552 KB | Output is correct |
| 9 | Correct | 2 ms | 684 KB | Output is correct |
| 10 | Correct | 3 ms | 684 KB | Output is correct |
| 11 | Correct | 2 ms | 684 KB | Output is correct |
| 12 | Correct | 2 ms | 684 KB | Output is correct |
| 13 | Correct | 3 ms | 684 KB | Output is correct |
| 14 | Correct | 4 ms | 684 KB | Output is correct |
| 15 | Correct | 3 ms | 684 KB | Output is correct |
| 16 | Correct | 3 ms | 684 KB | Output is correct |
| 17 | Correct | 2 ms | 684 KB | Output is correct |
| 18 | Correct | 2 ms | 684 KB | Output is correct |
| 19 | Correct | 4 ms | 684 KB | Output is correct |
| 20 | Correct | 3 ms | 684 KB | Output is correct |
| 21 | Correct | 2 ms | 684 KB | Output is correct |
| 22 | Correct | 4 ms | 684 KB | Output is correct |
| 23 | Correct | 4 ms | 788 KB | Output is correct |
| 24 | Correct | 5 ms | 788 KB | Output is correct |
| 25 | Correct | 4 ms | 788 KB | Output is correct |
| 26 | Correct | 5 ms | 788 KB | Output is correct |
| 27 | Correct | 4 ms | 788 KB | Output is correct |
| 28 | Correct | 4 ms | 788 KB | Output is correct |
| 29 | Correct | 4 ms | 788 KB | Output is correct |
| 30 | Execution timed out | 2057 ms | 21328 KB | Time limit exceeded |
| 31 | Halted | 0 ms | 0 KB | - |