Submission #423908

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
423908	2021-06-11T14:04:43 Z	2fat2code	Ancient Books (IOI17_books)	C++17	12 / 100	2 ms	332 KB

books

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

const int nmax = 1005;

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

long long compute(long long L, long long R){
    if(L <= l_ned && R >= r_ned) return 0LL;
    else{
        if(dp[L][R].sc == 1){
            return dp[L][R].fr;
        }
        else{
            dp[L][R].sc = 1;
            dp[L][R].fr = 1e18;
            if(L > 0){
                dp[L][R].fr = compute(min(L-1, extend[viz[L-1]].fr), max(R, extend[viz[L-1]].sc)) + 2LL;
            }
            else if(R < n-1){
                dp[L][R].fr = min(dp[L][R].fr, compute(min(L, extend[viz[R+1]].fr), max(R+1, extend[viz[R+1]].sc)) + 2LL);
            }
            return dp[L][R].fr;
        }
    }
}

long long *l[nmax], *r[nmax];

long long minimum_walk(vector<int> p, int s) {
	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]));
	}
	for(int i=1;i<=comp;i++){
        l[i] = &(cicles[i][0]);
        r[i] = &(cicles[i].back());
	}
    for(int i=0;i<=n-1;i++){
        for(int j=1;j<=comp;j++){
            if(cicles[j][0] <= i && cicles[j].back() >= i){
                if(*l[j] <= *l[viz[i]]){
                    l[viz[i]] = l[j];
                }
                else{
                    l[j] = l[viz[i]];
                }
                if(*r[viz[i]] <= *r[j]){
                    r[viz[i]] = r[j];
                }
                else{
                    r[j] = r[viz[i]];
                }
            }
        }
	}
	for(int i=1;i<=comp;i++){
        extend[i].fr = *l[i];
        extend[i].sc = *r[i];
	}
	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--;
	return compute(extend[viz[s]].fr, extend[viz[s]].sc) + ans;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Incorrect	1 ms	332 KB	3rd lines differ - on the 1st token, expected: '12988', found: '12990'
27	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Incorrect	1 ms	332 KB	3rd lines differ - on the 1st token, expected: '12988', found: '12990'
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	328 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Incorrect	1 ms	332 KB	3rd lines differ - on the 1st token, expected: '12988', found: '12990'
27	Halted	0 ms	0 KB	-

Submission #423908

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0