Submission #425916

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
425916	2021-06-13T12:21:42 Z	2fat2code	Ancient Books (IOI17_books)	C++17	50 / 100	361 ms	66624 KB

books

#include "books.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
#define LL long long
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 1000005;

long long n, comp, l_ned, r_ned, ans, viz[nmax];
vector<long long>cicles[nmax];

void extend(LL &l, LL &r, LL &ll, LL &rr){
    while(l > ll || r < rr){
        if(l > ll){
            --l;
            ll = min(ll, cicles[viz[l]][0]);
            rr = max(rr, cicles[viz[l]].back());
        }
        if(r < rr){
            ++r;
            ll = min(ll, cicles[viz[r]][0]);
            rr = max(rr, cicles[viz[r]].back());
        }
    }
}

void compute(int s){
    LL l = s, r = s, ll = cicles[viz[s]][0], rr = cicles[viz[s]].back();
    extend(l, r, ll, rr);
    while(ll > 0 || rr < n - 1){
        LL calcright = 0, maxi = -1, findright = 0;
        for(int i=rr+1;i<=n-1;i++){
            if(i == cicles[viz[i]][0] && i > maxi){
                calcright += 2LL;
            }
            maxi = max(maxi, cicles[viz[i]].back());
            if(cicles[viz[i]][0] < ll){
                findright = viz[i];
                break;
            }
        }
        if(!findright){
            rr = n - 1;
            ans += calcright;
        }
        LL calcleft = 0, mini = n, findleft = 0;
        for(int i=ll-1;i>=0;i--){
            if(i == cicles[viz[i]].back() && i < mini){
                calcleft += 2LL;
            }
            mini = min(mini, cicles[viz[i]][0]);
            if(cicles[viz[i]].back() > rr){
                findleft = viz[i];
                break;
            }
        }
        if(!findleft){
            ll = 0;
            ans += calcleft;
        }
        else{
            ans += min(calcleft, calcright);
            if(calcleft > calcright){
                ll = min(ll, cicles[findright][0]);
                rr = max(rr, cicles[findright].back());
            }
            else{
                ll = min(ll, cicles[findleft][0]);
                rr = max(rr, cicles[findleft].back());
            }
        }
        extend(l, r, ll, rr);
    }
}

long long minimum_walk(vector<int> p, int s) {
    n = (int)p.size();
	while(p[l_ned] == l_ned && s > l_ned) l_ned++;
	r_ned = n - 1;
	while(p[r_ned] == r_ned && s < r_ned) r_ned--;
	vector<int>aux;
	for(int i=l_ned;i<=r_ned;i++){
        aux.push_back(p[i] - l_ned);
	}
	swap(aux, p);
	s -= l_ned;
	n = (int)p.size();

	for(int i=0;i<n;i++){
        ans += abs(i - p[i]);
	}
	for(int i=0;i<n;i++){
        if(!viz[i]){
            ++comp;
            viz[i] = comp;
            cicles[comp].push_back(i);
            int curr = p[i];
            while(curr  !=  i){
                viz[curr] = comp;
                cicles[comp].push_back(curr);
                curr = p[curr];
            }
        }
	}
	for(int i=1;i<=comp;i++){
        sort(all(cicles[i]));
	}
	compute(s);
    return ans;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23756 KB	Output is correct
2	Correct	16 ms	23756 KB	Output is correct
3	Correct	18 ms	23732 KB	Output is correct
4	Correct	16 ms	23784 KB	Output is correct
5	Correct	16 ms	23740 KB	Output is correct
6	Correct	18 ms	23784 KB	Output is correct
7	Correct	18 ms	23704 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	16 ms	23752 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	17 ms	23680 KB	Output is correct
12	Correct	20 ms	23676 KB	Output is correct
13	Correct	17 ms	23784 KB	Output is correct
14	Correct	18 ms	23756 KB	Output is correct
15	Correct	17 ms	23668 KB	Output is correct
16	Correct	17 ms	23716 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23756 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23756 KB	Output is correct
2	Correct	16 ms	23756 KB	Output is correct
3	Correct	18 ms	23732 KB	Output is correct
4	Correct	16 ms	23784 KB	Output is correct
5	Correct	16 ms	23740 KB	Output is correct
6	Correct	18 ms	23784 KB	Output is correct
7	Correct	18 ms	23704 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	16 ms	23752 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	17 ms	23680 KB	Output is correct
12	Correct	20 ms	23676 KB	Output is correct
13	Correct	17 ms	23784 KB	Output is correct
14	Correct	18 ms	23756 KB	Output is correct
15	Correct	17 ms	23668 KB	Output is correct
16	Correct	17 ms	23716 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23756 KB	Output is correct
19	Correct	15 ms	23728 KB	Output is correct
20	Correct	15 ms	23820 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	19 ms	23756 KB	Output is correct
23	Correct	18 ms	23776 KB	Output is correct
24	Correct	18 ms	23756 KB	Output is correct
25	Correct	15 ms	23728 KB	Output is correct
26	Correct	16 ms	23756 KB	Output is correct
27	Correct	18 ms	23724 KB	Output is correct
28	Correct	16 ms	23764 KB	Output is correct
29	Correct	18 ms	23828 KB	Output is correct

Subtask #3
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23756 KB	Output is correct
2	Correct	16 ms	23756 KB	Output is correct
3	Correct	18 ms	23732 KB	Output is correct
4	Correct	16 ms	23784 KB	Output is correct
5	Correct	16 ms	23740 KB	Output is correct
6	Correct	18 ms	23784 KB	Output is correct
7	Correct	18 ms	23704 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	16 ms	23752 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	17 ms	23680 KB	Output is correct
12	Correct	20 ms	23676 KB	Output is correct
13	Correct	17 ms	23784 KB	Output is correct
14	Correct	18 ms	23756 KB	Output is correct
15	Correct	17 ms	23668 KB	Output is correct
16	Correct	17 ms	23716 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23756 KB	Output is correct
19	Correct	15 ms	23728 KB	Output is correct
20	Correct	15 ms	23820 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	19 ms	23756 KB	Output is correct
23	Correct	18 ms	23776 KB	Output is correct
24	Correct	18 ms	23756 KB	Output is correct
25	Correct	15 ms	23728 KB	Output is correct
26	Correct	16 ms	23756 KB	Output is correct
27	Correct	18 ms	23724 KB	Output is correct
28	Correct	16 ms	23764 KB	Output is correct
29	Correct	18 ms	23828 KB	Output is correct
30	Correct	361 ms	53132 KB	Output is correct
31	Correct	332 ms	53004 KB	Output is correct
32	Correct	135 ms	31556 KB	Output is correct
33	Correct	223 ms	66468 KB	Output is correct
34	Correct	220 ms	66452 KB	Output is correct
35	Correct	227 ms	63376 KB	Output is correct
36	Correct	216 ms	58148 KB	Output is correct
37	Correct	210 ms	54948 KB	Output is correct
38	Correct	228 ms	54192 KB	Output is correct
39	Correct	223 ms	53916 KB	Output is correct
40	Correct	229 ms	52664 KB	Output is correct
41	Correct	262 ms	53012 KB	Output is correct
42	Correct	265 ms	52624 KB	Output is correct
43	Correct	227 ms	66624 KB	Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23756 KB	Output is correct
2	Correct	16 ms	23756 KB	Output is correct
3	Correct	18 ms	23732 KB	Output is correct
4	Correct	16 ms	23784 KB	Output is correct
5	Correct	16 ms	23740 KB	Output is correct
6	Correct	18 ms	23784 KB	Output is correct
7	Correct	18 ms	23704 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	16 ms	23752 KB	Output is correct
10	Correct	15 ms	23788 KB	Output is correct
11	Correct	17 ms	23680 KB	Output is correct
12	Correct	20 ms	23676 KB	Output is correct
13	Correct	17 ms	23784 KB	Output is correct
14	Correct	18 ms	23756 KB	Output is correct
15	Correct	17 ms	23668 KB	Output is correct
16	Correct	17 ms	23716 KB	Output is correct
17	Correct	15 ms	23756 KB	Output is correct
18	Correct	19 ms	23756 KB	Output is correct
19	Correct	15 ms	23728 KB	Output is correct
20	Correct	15 ms	23820 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	19 ms	23756 KB	Output is correct
23	Correct	18 ms	23776 KB	Output is correct
24	Correct	18 ms	23756 KB	Output is correct
25	Correct	15 ms	23728 KB	Output is correct
26	Correct	16 ms	23756 KB	Output is correct
27	Correct	18 ms	23724 KB	Output is correct
28	Correct	16 ms	23764 KB	Output is correct
29	Correct	18 ms	23828 KB	Output is correct
30	Correct	361 ms	53132 KB	Output is correct
31	Correct	332 ms	53004 KB	Output is correct
32	Correct	135 ms	31556 KB	Output is correct
33	Correct	223 ms	66468 KB	Output is correct
34	Correct	220 ms	66452 KB	Output is correct
35	Correct	227 ms	63376 KB	Output is correct
36	Correct	216 ms	58148 KB	Output is correct
37	Correct	210 ms	54948 KB	Output is correct
38	Correct	228 ms	54192 KB	Output is correct
39	Correct	223 ms	53916 KB	Output is correct
40	Correct	229 ms	52664 KB	Output is correct
41	Correct	262 ms	53012 KB	Output is correct
42	Correct	265 ms	52624 KB	Output is correct
43	Correct	227 ms	66624 KB	Output is correct
44	Incorrect	18 ms	23756 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3302'
45	Halted	0 ms	0 KB	-

Submission #425916

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