답안 #425856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425856	2021-06-13T12:01:15 Z	2fat2code	고대 책들 (IOI17_books)	C++17	50 / 100	353 ms	66664 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){
        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{
            assert(1 == 0);
            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	19 ms	23756 KB	Output is correct
2	Correct	18 ms	23792 KB	Output is correct
3	Correct	16 ms	23784 KB	Output is correct
4	Correct	17 ms	23756 KB	Output is correct
5	Correct	18 ms	23732 KB	Output is correct
6	Correct	18 ms	23724 KB	Output is correct
7	Correct	18 ms	23756 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	18 ms	23756 KB	Output is correct
11	Correct	19 ms	23688 KB	Output is correct
12	Correct	18 ms	23700 KB	Output is correct
13	Correct	18 ms	23756 KB	Output is correct
14	Correct	17 ms	23708 KB	Output is correct
15	Correct	15 ms	23664 KB	Output is correct
16	Correct	16 ms	23784 KB	Output is correct
17	Correct	18 ms	23756 KB	Output is correct
18	Correct	18 ms	23708 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	23756 KB	Output is correct
2	Correct	18 ms	23792 KB	Output is correct
3	Correct	16 ms	23784 KB	Output is correct
4	Correct	17 ms	23756 KB	Output is correct
5	Correct	18 ms	23732 KB	Output is correct
6	Correct	18 ms	23724 KB	Output is correct
7	Correct	18 ms	23756 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	18 ms	23756 KB	Output is correct
11	Correct	19 ms	23688 KB	Output is correct
12	Correct	18 ms	23700 KB	Output is correct
13	Correct	18 ms	23756 KB	Output is correct
14	Correct	17 ms	23708 KB	Output is correct
15	Correct	15 ms	23664 KB	Output is correct
16	Correct	16 ms	23784 KB	Output is correct
17	Correct	18 ms	23756 KB	Output is correct
18	Correct	18 ms	23708 KB	Output is correct
19	Correct	18 ms	23784 KB	Output is correct
20	Correct	17 ms	23756 KB	Output is correct
21	Correct	17 ms	23800 KB	Output is correct
22	Correct	16 ms	23816 KB	Output is correct
23	Correct	19 ms	23724 KB	Output is correct
24	Correct	16 ms	23756 KB	Output is correct
25	Correct	18 ms	23792 KB	Output is correct
26	Correct	15 ms	23784 KB	Output is correct
27	Correct	17 ms	23728 KB	Output is correct
28	Correct	18 ms	23756 KB	Output is correct
29	Correct	18 ms	23716 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	23756 KB	Output is correct
2	Correct	18 ms	23792 KB	Output is correct
3	Correct	16 ms	23784 KB	Output is correct
4	Correct	17 ms	23756 KB	Output is correct
5	Correct	18 ms	23732 KB	Output is correct
6	Correct	18 ms	23724 KB	Output is correct
7	Correct	18 ms	23756 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	18 ms	23756 KB	Output is correct
11	Correct	19 ms	23688 KB	Output is correct
12	Correct	18 ms	23700 KB	Output is correct
13	Correct	18 ms	23756 KB	Output is correct
14	Correct	17 ms	23708 KB	Output is correct
15	Correct	15 ms	23664 KB	Output is correct
16	Correct	16 ms	23784 KB	Output is correct
17	Correct	18 ms	23756 KB	Output is correct
18	Correct	18 ms	23708 KB	Output is correct
19	Correct	18 ms	23784 KB	Output is correct
20	Correct	17 ms	23756 KB	Output is correct
21	Correct	17 ms	23800 KB	Output is correct
22	Correct	16 ms	23816 KB	Output is correct
23	Correct	19 ms	23724 KB	Output is correct
24	Correct	16 ms	23756 KB	Output is correct
25	Correct	18 ms	23792 KB	Output is correct
26	Correct	15 ms	23784 KB	Output is correct
27	Correct	17 ms	23728 KB	Output is correct
28	Correct	18 ms	23756 KB	Output is correct
29	Correct	18 ms	23716 KB	Output is correct
30	Correct	353 ms	53152 KB	Output is correct
31	Correct	329 ms	53016 KB	Output is correct
32	Correct	131 ms	31532 KB	Output is correct
33	Correct	226 ms	66388 KB	Output is correct
34	Correct	233 ms	66452 KB	Output is correct
35	Correct	222 ms	63380 KB	Output is correct
36	Correct	209 ms	58272 KB	Output is correct
37	Correct	235 ms	54932 KB	Output is correct
38	Correct	224 ms	54164 KB	Output is correct
39	Correct	211 ms	53924 KB	Output is correct
40	Correct	224 ms	52632 KB	Output is correct
41	Correct	262 ms	53036 KB	Output is correct
42	Correct	269 ms	52756 KB	Output is correct
43	Correct	244 ms	66664 KB	Output is correct

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	105 ms	48068 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	23756 KB	Output is correct
2	Correct	18 ms	23792 KB	Output is correct
3	Correct	16 ms	23784 KB	Output is correct
4	Correct	17 ms	23756 KB	Output is correct
5	Correct	18 ms	23732 KB	Output is correct
6	Correct	18 ms	23724 KB	Output is correct
7	Correct	18 ms	23756 KB	Output is correct
8	Correct	16 ms	23756 KB	Output is correct
9	Correct	15 ms	23756 KB	Output is correct
10	Correct	18 ms	23756 KB	Output is correct
11	Correct	19 ms	23688 KB	Output is correct
12	Correct	18 ms	23700 KB	Output is correct
13	Correct	18 ms	23756 KB	Output is correct
14	Correct	17 ms	23708 KB	Output is correct
15	Correct	15 ms	23664 KB	Output is correct
16	Correct	16 ms	23784 KB	Output is correct
17	Correct	18 ms	23756 KB	Output is correct
18	Correct	18 ms	23708 KB	Output is correct
19	Correct	18 ms	23784 KB	Output is correct
20	Correct	17 ms	23756 KB	Output is correct
21	Correct	17 ms	23800 KB	Output is correct
22	Correct	16 ms	23816 KB	Output is correct
23	Correct	19 ms	23724 KB	Output is correct
24	Correct	16 ms	23756 KB	Output is correct
25	Correct	18 ms	23792 KB	Output is correct
26	Correct	15 ms	23784 KB	Output is correct
27	Correct	17 ms	23728 KB	Output is correct
28	Correct	18 ms	23756 KB	Output is correct
29	Correct	18 ms	23716 KB	Output is correct
30	Correct	353 ms	53152 KB	Output is correct
31	Correct	329 ms	53016 KB	Output is correct
32	Correct	131 ms	31532 KB	Output is correct
33	Correct	226 ms	66388 KB	Output is correct
34	Correct	233 ms	66452 KB	Output is correct
35	Correct	222 ms	63380 KB	Output is correct
36	Correct	209 ms	58272 KB	Output is correct
37	Correct	235 ms	54932 KB	Output is correct
38	Correct	224 ms	54164 KB	Output is correct
39	Correct	211 ms	53924 KB	Output is correct
40	Correct	224 ms	52632 KB	Output is correct
41	Correct	262 ms	53036 KB	Output is correct
42	Correct	269 ms	52756 KB	Output is correct
43	Correct	244 ms	66664 KB	Output is correct
44	Runtime error	105 ms	48068 KB	Execution killed with signal 6
45	Halted	0 ms	0 KB	-