Submission #292782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
292782	2020-09-07T13:24:46 Z	shayan_p	Ancient Books (IOI17_books)	C++17	22 / 100	2000 ms	12024 KB

books

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "books.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int cnt[maxn];

ll minimum_walk(vector<int> p, int s){
    int n = sz(p);
    assert(s == 0);
    memset(cnt, 0, sizeof cnt);
    ll ans = 0;
    while(n > 1 && p[n-1] == n-1)
	n--, p.pop_back();
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	while(l < r)
	    cnt[l] = 1, l++;
    }
    /*
    int sm = 0;
    for(int i = 0; i < n-1; i++){
	sm+= cnt[i];
	ans+= (sm > 0 ? 0 : 2);
	}*/
    for(int i = 0; i < n-1; i++){
	ans+= cnt[i] == 0 ? 2 : 0;
    }
    return ans;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4224 KB	Output is correct
11	Correct	3 ms	4224 KB	Output is correct
12	Correct	3 ms	4224 KB	Output is correct
13	Correct	3 ms	4224 KB	Output is correct
14	Correct	3 ms	4224 KB	Output is correct
15	Correct	3 ms	4224 KB	Output is correct
16	Correct	3 ms	4224 KB	Output is correct
17	Correct	3 ms	4224 KB	Output is correct
18	Correct	3 ms	4224 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4224 KB	Output is correct
11	Correct	3 ms	4224 KB	Output is correct
12	Correct	3 ms	4224 KB	Output is correct
13	Correct	3 ms	4224 KB	Output is correct
14	Correct	3 ms	4224 KB	Output is correct
15	Correct	3 ms	4224 KB	Output is correct
16	Correct	3 ms	4224 KB	Output is correct
17	Correct	3 ms	4224 KB	Output is correct
18	Correct	3 ms	4224 KB	Output is correct
19	Correct	3 ms	4224 KB	Output is correct
20	Correct	3 ms	4224 KB	Output is correct
21	Correct	3 ms	4224 KB	Output is correct
22	Correct	3 ms	4224 KB	Output is correct
23	Correct	3 ms	4224 KB	Output is correct
24	Correct	4 ms	4224 KB	Output is correct
25	Correct	3 ms	4224 KB	Output is correct
26	Correct	3 ms	4224 KB	Output is correct
27	Correct	3 ms	4224 KB	Output is correct
28	Correct	3 ms	4224 KB	Output is correct
29	Correct	3 ms	4224 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4224 KB	Output is correct
11	Correct	3 ms	4224 KB	Output is correct
12	Correct	3 ms	4224 KB	Output is correct
13	Correct	3 ms	4224 KB	Output is correct
14	Correct	3 ms	4224 KB	Output is correct
15	Correct	3 ms	4224 KB	Output is correct
16	Correct	3 ms	4224 KB	Output is correct
17	Correct	3 ms	4224 KB	Output is correct
18	Correct	3 ms	4224 KB	Output is correct
19	Correct	3 ms	4224 KB	Output is correct
20	Correct	3 ms	4224 KB	Output is correct
21	Correct	3 ms	4224 KB	Output is correct
22	Correct	3 ms	4224 KB	Output is correct
23	Correct	3 ms	4224 KB	Output is correct
24	Correct	4 ms	4224 KB	Output is correct
25	Correct	3 ms	4224 KB	Output is correct
26	Correct	3 ms	4224 KB	Output is correct
27	Correct	3 ms	4224 KB	Output is correct
28	Correct	3 ms	4224 KB	Output is correct
29	Correct	3 ms	4224 KB	Output is correct
30	Execution timed out	2070 ms	12024 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	512 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4224 KB	Output is correct
2	Correct	3 ms	4224 KB	Output is correct
3	Correct	3 ms	4224 KB	Output is correct
4	Correct	3 ms	4224 KB	Output is correct
5	Correct	3 ms	4224 KB	Output is correct
6	Correct	3 ms	4224 KB	Output is correct
7	Correct	3 ms	4224 KB	Output is correct
8	Correct	3 ms	4224 KB	Output is correct
9	Correct	3 ms	4352 KB	Output is correct
10	Correct	3 ms	4224 KB	Output is correct
11	Correct	3 ms	4224 KB	Output is correct
12	Correct	3 ms	4224 KB	Output is correct
13	Correct	3 ms	4224 KB	Output is correct
14	Correct	3 ms	4224 KB	Output is correct
15	Correct	3 ms	4224 KB	Output is correct
16	Correct	3 ms	4224 KB	Output is correct
17	Correct	3 ms	4224 KB	Output is correct
18	Correct	3 ms	4224 KB	Output is correct
19	Correct	3 ms	4224 KB	Output is correct
20	Correct	3 ms	4224 KB	Output is correct
21	Correct	3 ms	4224 KB	Output is correct
22	Correct	3 ms	4224 KB	Output is correct
23	Correct	3 ms	4224 KB	Output is correct
24	Correct	4 ms	4224 KB	Output is correct
25	Correct	3 ms	4224 KB	Output is correct
26	Correct	3 ms	4224 KB	Output is correct
27	Correct	3 ms	4224 KB	Output is correct
28	Correct	3 ms	4224 KB	Output is correct
29	Correct	3 ms	4224 KB	Output is correct
30	Execution timed out	2070 ms	12024 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-