Submission #294947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
294947	2020-09-09T11:01:57 Z	shayan_p	Ancient Books (IOI17_books)	C++17	50 / 100	306 ms	32252 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 pr[maxn], L[maxn], R[maxn];
int pr2[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
    if( (a = fnd(a)) == (b = fnd(b)) )
	return;
    if(pr[a] > pr[b])
	swap(a, b);
    L[a] = min(L[a], L[b]);
    R[a] = max(R[a], R[b]);
    pr[a]+= pr[b];
    pr[b] = a;	    
}
 
ll minimum_walk(vector<int> p, int s){
    memset(pr, -1, sizeof pr);
    memset(pr2, -1, sizeof pr2);

    iota(L, L + maxn, 0);
    iota(R, R + maxn, 0);
    
    int n = sz(p);
    ll ans = 0;
 
    for(int i = 0; i < n; i++){
	int l = i, r = p[i];
	if(l > r)
	    swap(l, r);
	ans+= r-l;
	mrg(l, r);
    }
    vector<int> vec;
    for(int i = 0; i < n; i++){
	if(fnd(i) == i)
	    vec.PB(i);
    }
    sort(vec.begin(), vec.end(), [&](int i, int j){ return L[fnd(i)] > L[fnd(j)]; });
    for(int id : vec){
	int tmp = R[id];
	while(tmp != -1){
	    mrg(id, tmp);
	    int nx = pr2[tmp];
	    pr2[tmp] = id;
	    tmp = nx;
	}
    }
    
    int l = s, r = s;
    while(true){
	while(true){
	    bool is = 0;
	    while(r < R[fnd(s)])
		mrg(s, ++r), is = 1;
	    while(l > L[fnd(s)])
		mrg(s, --l), is = 1;
	    if(!is)
		break;
	}
	int d1 = 0, d2 = 0;
	while(r < n && L[fnd(s)] <= L[fnd(r)]){
	    d2+= R[fnd(s)] < r;
	    mrg(s, r);
	    r++;
	}
	while(l >= 0 && R[fnd(l)] <= R[fnd(s)]){
	    d1+= L[fnd(s)] > l;
	    mrg(s, l);
	    l--;
	}
	if(l == -1 || r == n){
	    assert(l == -1 && r == n);
	    ans+= 2 * (d1 + d2);
	    break;
	}
	else{
	    ans+= 2 * min(d1 + 1, d2 + 1);
	    assert(fnd(l) == fnd(r));
	    mrg(s, l);
	    mrg(s, r);
	}	    
    }
    for(int i = 0; i < s && p[i] == i; i++){
	ans-= 2;
    }
    for(int i = n-1; i > s && p[i] == i; i--){
	ans-= 2;
    }
    return ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16000 KB	Output is correct
2	Correct	11 ms	16000 KB	Output is correct
3	Correct	10 ms	16000 KB	Output is correct
4	Correct	10 ms	16000 KB	Output is correct
5	Correct	10 ms	16128 KB	Output is correct
6	Correct	11 ms	16000 KB	Output is correct
7	Correct	12 ms	16000 KB	Output is correct
8	Correct	10 ms	16000 KB	Output is correct
9	Correct	10 ms	16000 KB	Output is correct
10	Correct	11 ms	16000 KB	Output is correct
11	Correct	10 ms	16000 KB	Output is correct
12	Correct	11 ms	16000 KB	Output is correct
13	Correct	12 ms	16000 KB	Output is correct
14	Correct	10 ms	16000 KB	Output is correct
15	Correct	11 ms	16000 KB	Output is correct
16	Correct	10 ms	16000 KB	Output is correct
17	Correct	11 ms	16000 KB	Output is correct
18	Correct	11 ms	16000 KB	Output is correct
19	Correct	11 ms	16000 KB	Output is correct
20	Correct	11 ms	16000 KB	Output is correct
21	Correct	11 ms	16016 KB	Output is correct
22	Correct	10 ms	16000 KB	Output is correct
23	Correct	11 ms	16000 KB	Output is correct
24	Correct	11 ms	16000 KB	Output is correct
25	Correct	11 ms	16000 KB	Output is correct
26	Correct	12 ms	16000 KB	Output is correct
27	Correct	11 ms	16000 KB	Output is correct
28	Correct	11 ms	16000 KB	Output is correct
29	Correct	12 ms	16000 KB	Output is correct
30	Correct	298 ms	24824 KB	Output is correct
31	Correct	306 ms	24832 KB	Output is correct
32	Correct	231 ms	29032 KB	Output is correct
33	Correct	237 ms	29032 KB	Output is correct
34	Correct	236 ms	29032 KB	Output is correct
35	Correct	234 ms	29040 KB	Output is correct
36	Correct	229 ms	25880 KB	Output is correct
37	Correct	219 ms	25104 KB	Output is correct
38	Correct	220 ms	24952 KB	Output is correct
39	Correct	217 ms	24824 KB	Output is correct
40	Correct	221 ms	24828 KB	Output is correct
41	Correct	250 ms	24824 KB	Output is correct
42	Correct	245 ms	24952 KB	Output is correct
43	Correct	274 ms	29032 KB	Output is correct

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	16000 KB	Output is correct
2	Runtime error	34 ms	32252 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16000 KB	Output is correct
2	Correct	11 ms	16000 KB	Output is correct
3	Correct	10 ms	16000 KB	Output is correct
4	Correct	10 ms	16000 KB	Output is correct
5	Correct	10 ms	16128 KB	Output is correct
6	Correct	11 ms	16000 KB	Output is correct
7	Correct	12 ms	16000 KB	Output is correct
8	Correct	10 ms	16000 KB	Output is correct
9	Correct	10 ms	16000 KB	Output is correct
10	Correct	11 ms	16000 KB	Output is correct
11	Correct	10 ms	16000 KB	Output is correct
12	Correct	11 ms	16000 KB	Output is correct
13	Correct	12 ms	16000 KB	Output is correct
14	Correct	10 ms	16000 KB	Output is correct
15	Correct	11 ms	16000 KB	Output is correct
16	Correct	10 ms	16000 KB	Output is correct
17	Correct	11 ms	16000 KB	Output is correct
18	Correct	11 ms	16000 KB	Output is correct
19	Correct	11 ms	16000 KB	Output is correct
20	Correct	11 ms	16000 KB	Output is correct
21	Correct	11 ms	16016 KB	Output is correct
22	Correct	10 ms	16000 KB	Output is correct
23	Correct	11 ms	16000 KB	Output is correct
24	Correct	11 ms	16000 KB	Output is correct
25	Correct	11 ms	16000 KB	Output is correct
26	Correct	12 ms	16000 KB	Output is correct
27	Correct	11 ms	16000 KB	Output is correct
28	Correct	11 ms	16000 KB	Output is correct
29	Correct	12 ms	16000 KB	Output is correct
30	Correct	298 ms	24824 KB	Output is correct
31	Correct	306 ms	24832 KB	Output is correct
32	Correct	231 ms	29032 KB	Output is correct
33	Correct	237 ms	29032 KB	Output is correct
34	Correct	236 ms	29032 KB	Output is correct
35	Correct	234 ms	29040 KB	Output is correct
36	Correct	229 ms	25880 KB	Output is correct
37	Correct	219 ms	25104 KB	Output is correct
38	Correct	220 ms	24952 KB	Output is correct
39	Correct	217 ms	24824 KB	Output is correct
40	Correct	221 ms	24828 KB	Output is correct
41	Correct	250 ms	24824 KB	Output is correct
42	Correct	245 ms	24952 KB	Output is correct
43	Correct	274 ms	29032 KB	Output is correct
44	Correct	11 ms	16000 KB	Output is correct
45	Runtime error	34 ms	32252 KB	Execution killed with signal 11
46	Halted	0 ms	0 KB	-

Submission #294947

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0