답안 #425869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425869	2021-06-13T12:07:16 Z	2fat2code	고대 책들 (IOI17_books)	C++17	50 / 100	334 ms	66580 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());
        }
        else 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){
        extend(l, r, ll, rr);
        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());
            }
        }
    }
}

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

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23684 KB	Output is correct
2	Correct	13 ms	23756 KB	Output is correct
3	Correct	13 ms	23704 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	21 ms	23748 KB	Output is correct
6	Correct	13 ms	23788 KB	Output is correct
7	Correct	20 ms	23756 KB	Output is correct
8	Correct	20 ms	23728 KB	Output is correct
9	Correct	13 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23700 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	14 ms	23692 KB	Output is correct
14	Correct	15 ms	23760 KB	Output is correct
15	Correct	15 ms	23756 KB	Output is correct
16	Correct	14 ms	23784 KB	Output is correct
17	Correct	15 ms	23788 KB	Output is correct
18	Correct	17 ms	23712 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23684 KB	Output is correct
2	Correct	13 ms	23756 KB	Output is correct
3	Correct	13 ms	23704 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	21 ms	23748 KB	Output is correct
6	Correct	13 ms	23788 KB	Output is correct
7	Correct	20 ms	23756 KB	Output is correct
8	Correct	20 ms	23728 KB	Output is correct
9	Correct	13 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23700 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	14 ms	23692 KB	Output is correct
14	Correct	15 ms	23760 KB	Output is correct
15	Correct	15 ms	23756 KB	Output is correct
16	Correct	14 ms	23784 KB	Output is correct
17	Correct	15 ms	23788 KB	Output is correct
18	Correct	17 ms	23712 KB	Output is correct
19	Correct	14 ms	23756 KB	Output is correct
20	Correct	20 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23820 KB	Output is correct
23	Correct	16 ms	23808 KB	Output is correct
24	Correct	14 ms	23756 KB	Output is correct
25	Correct	16 ms	23756 KB	Output is correct
26	Correct	17 ms	23756 KB	Output is correct
27	Correct	14 ms	23756 KB	Output is correct
28	Correct	15 ms	23744 KB	Output is correct
29	Correct	14 ms	23816 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23684 KB	Output is correct
2	Correct	13 ms	23756 KB	Output is correct
3	Correct	13 ms	23704 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	21 ms	23748 KB	Output is correct
6	Correct	13 ms	23788 KB	Output is correct
7	Correct	20 ms	23756 KB	Output is correct
8	Correct	20 ms	23728 KB	Output is correct
9	Correct	13 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23700 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	14 ms	23692 KB	Output is correct
14	Correct	15 ms	23760 KB	Output is correct
15	Correct	15 ms	23756 KB	Output is correct
16	Correct	14 ms	23784 KB	Output is correct
17	Correct	15 ms	23788 KB	Output is correct
18	Correct	17 ms	23712 KB	Output is correct
19	Correct	14 ms	23756 KB	Output is correct
20	Correct	20 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23820 KB	Output is correct
23	Correct	16 ms	23808 KB	Output is correct
24	Correct	14 ms	23756 KB	Output is correct
25	Correct	16 ms	23756 KB	Output is correct
26	Correct	17 ms	23756 KB	Output is correct
27	Correct	14 ms	23756 KB	Output is correct
28	Correct	15 ms	23744 KB	Output is correct
29	Correct	14 ms	23816 KB	Output is correct
30	Correct	315 ms	53196 KB	Output is correct
31	Correct	334 ms	52936 KB	Output is correct
32	Correct	142 ms	31544 KB	Output is correct
33	Correct	248 ms	66456 KB	Output is correct
34	Correct	305 ms	66492 KB	Output is correct
35	Correct	253 ms	63404 KB	Output is correct
36	Correct	200 ms	58160 KB	Output is correct
37	Correct	224 ms	54932 KB	Output is correct
38	Correct	220 ms	54168 KB	Output is correct
39	Correct	303 ms	53908 KB	Output is correct
40	Correct	227 ms	52656 KB	Output is correct
41	Correct	295 ms	53188 KB	Output is correct
42	Correct	244 ms	52652 KB	Output is correct
43	Correct	221 ms	66580 KB	Output is correct

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	14 ms	23764 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3302'
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23684 KB	Output is correct
2	Correct	13 ms	23756 KB	Output is correct
3	Correct	13 ms	23704 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	21 ms	23748 KB	Output is correct
6	Correct	13 ms	23788 KB	Output is correct
7	Correct	20 ms	23756 KB	Output is correct
8	Correct	20 ms	23728 KB	Output is correct
9	Correct	13 ms	23756 KB	Output is correct
10	Correct	15 ms	23756 KB	Output is correct
11	Correct	15 ms	23700 KB	Output is correct
12	Correct	15 ms	23756 KB	Output is correct
13	Correct	14 ms	23692 KB	Output is correct
14	Correct	15 ms	23760 KB	Output is correct
15	Correct	15 ms	23756 KB	Output is correct
16	Correct	14 ms	23784 KB	Output is correct
17	Correct	15 ms	23788 KB	Output is correct
18	Correct	17 ms	23712 KB	Output is correct
19	Correct	14 ms	23756 KB	Output is correct
20	Correct	20 ms	23756 KB	Output is correct
21	Correct	15 ms	23756 KB	Output is correct
22	Correct	16 ms	23820 KB	Output is correct
23	Correct	16 ms	23808 KB	Output is correct
24	Correct	14 ms	23756 KB	Output is correct
25	Correct	16 ms	23756 KB	Output is correct
26	Correct	17 ms	23756 KB	Output is correct
27	Correct	14 ms	23756 KB	Output is correct
28	Correct	15 ms	23744 KB	Output is correct
29	Correct	14 ms	23816 KB	Output is correct
30	Correct	315 ms	53196 KB	Output is correct
31	Correct	334 ms	52936 KB	Output is correct
32	Correct	142 ms	31544 KB	Output is correct
33	Correct	248 ms	66456 KB	Output is correct
34	Correct	305 ms	66492 KB	Output is correct
35	Correct	253 ms	63404 KB	Output is correct
36	Correct	200 ms	58160 KB	Output is correct
37	Correct	224 ms	54932 KB	Output is correct
38	Correct	220 ms	54168 KB	Output is correct
39	Correct	303 ms	53908 KB	Output is correct
40	Correct	227 ms	52656 KB	Output is correct
41	Correct	295 ms	53188 KB	Output is correct
42	Correct	244 ms	52652 KB	Output is correct
43	Correct	221 ms	66580 KB	Output is correct
44	Incorrect	14 ms	23764 KB	3rd lines differ - on the 1st token, expected: '3304', found: '3302'
45	Halted	0 ms	0 KB	-

답안 #425869

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