답안 #521322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521322	2022-02-01T17:00:27 Z	ymm	고대 책들 (IOI17_books)	C++17	50 / 100	518 ms	71172 KB

books

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

#include "books.h"

const int N = 1'000'010;
int col[N]; int cnt=0;
int mn[N], mx[N];

ll minimum_walk(vector<int> p, int s) {
	int n = p.size();
	fill(col,col+N,-1);
	fill(mn,mn+N,N);
	fill(mx,mx+N,0);
	cnt=0;
	Loop(i,0,n){
		if(col[i]<0){
			int j = i;
			while(col[j]<0){
				mn[cnt] = min(mn[cnt], j);
				mx[cnt] = max(mx[cnt], j);
				col[j] = cnt;
				j = p[j];
			}
			++cnt;
		}
	}
	int l=0, r=n-1;
	while(l<s && p[l]==l) ++l;
	while(r>s && p[r]==r) --r;
//	Loop(i,0,n) cout << col[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mx[i] << ' '; cout << '\n';
//	Loop(i,0,cnt) cout << mn[i] << ' '; cout << '\n';
	int mnrt=s,mxrt=s,droot=0;
	// bfs
	{
		vector<int> dis(n, N);
		set<int> cand; Loop(i,l,r+1) cand.insert(i);
		deque<pii> q; q.emplace_back(col[s], 0); dis[col[s]]=0;
		while(q.size()){
			auto [v, d] = q.front(); q.pop_front();
			if(d != dis[v]) continue;
			int mn = ::mn[v], mx = ::mx[v];
			if(d==droot){ mnrt=min(mn,mnrt); mxrt=max(mx,mxrt); }
			else if(mn<=mnrt&&mxrt<=mx){droot=d; mnrt=mn; mxrt=mx;}
			for(;;){
				int i;
				auto it = cand.lower_bound(mn);
				if(it == cand.end() || (i = *it) > mx) break;
//				cout<<i<<"!\n";
				cand.erase(it);
				if(d < dis[i = col[i]]){
					dis[i] = d;
					q.emplace_front(i, d);
				}
			}
			if(l<mn && d+1<dis[col[mn-1]]){
				dis[col[mn-1]] = d+1;
				q.emplace_back(col[mn-1], d+1);
			}
			if(mx<r && d+1<dis[col[mx+1]]){
				dis[col[mx+1]] = d+1;
				q.emplace_back(col[mx+1], d+1);
			}
		}
	}
//	cout << mnrt << ' ' << mxrt << ' ' << droot << '\n';
	ll ans = 0;
	Loop(i,l,r+1) ans += abs(i-p[i]);
	int foo=0;
	Loop(i,mxrt+1,r+1) {
		droot += !foo;
		foo += i==mn[col[i]];
		foo -= i==mx[col[i]];
	}
	foo=0;
	LoopR(i,l,mnrt){
		droot += !foo;
		foo += i==mx[col[i]];
		foo -= i==mn[col[i]];
	}
	return ans+2*droot;
}

//int main()
//{
//	/*vector<int> p = {0, 1, 2, 3};
//	do{
//		if(minimum_walk(p,0)==8){
//			for(int x : p) cout << x << ' ';
//			cout << '\n';
//		}
//	}while(next_permutation(p.begin(), p.end()));*/
//	cout << minimum_walk({5, 1, 2, 3, 4, 0}, 3) << '\n';
//}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	11980 KB	Output is correct
2	Correct	5 ms	11980 KB	Output is correct
3	Correct	6 ms	11980 KB	Output is correct
4	Correct	6 ms	11980 KB	Output is correct
5	Correct	6 ms	11980 KB	Output is correct
6	Correct	6 ms	11960 KB	Output is correct
7	Correct	6 ms	11948 KB	Output is correct
8	Correct	6 ms	11980 KB	Output is correct
9	Correct	7 ms	11924 KB	Output is correct
10	Correct	5 ms	11980 KB	Output is correct
11	Correct	6 ms	11980 KB	Output is correct
12	Correct	5 ms	11980 KB	Output is correct
13	Correct	6 ms	11980 KB	Output is correct
14	Correct	6 ms	11980 KB	Output is correct
15	Correct	6 ms	11944 KB	Output is correct
16	Correct	6 ms	11980 KB	Output is correct
17	Correct	6 ms	11980 KB	Output is correct
18	Correct	8 ms	12036 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	11980 KB	Output is correct
2	Correct	5 ms	11980 KB	Output is correct
3	Correct	6 ms	11980 KB	Output is correct
4	Correct	6 ms	11980 KB	Output is correct
5	Correct	6 ms	11980 KB	Output is correct
6	Correct	6 ms	11960 KB	Output is correct
7	Correct	6 ms	11948 KB	Output is correct
8	Correct	6 ms	11980 KB	Output is correct
9	Correct	7 ms	11924 KB	Output is correct
10	Correct	5 ms	11980 KB	Output is correct
11	Correct	6 ms	11980 KB	Output is correct
12	Correct	5 ms	11980 KB	Output is correct
13	Correct	6 ms	11980 KB	Output is correct
14	Correct	6 ms	11980 KB	Output is correct
15	Correct	6 ms	11944 KB	Output is correct
16	Correct	6 ms	11980 KB	Output is correct
17	Correct	6 ms	11980 KB	Output is correct
18	Correct	8 ms	12036 KB	Output is correct
19	Correct	9 ms	11980 KB	Output is correct
20	Correct	7 ms	12072 KB	Output is correct
21	Correct	5 ms	11980 KB	Output is correct
22	Correct	7 ms	11980 KB	Output is correct
23	Correct	6 ms	12092 KB	Output is correct
24	Correct	6 ms	11980 KB	Output is correct
25	Correct	6 ms	11980 KB	Output is correct
26	Correct	6 ms	11980 KB	Output is correct
27	Correct	6 ms	11980 KB	Output is correct
28	Correct	6 ms	12108 KB	Output is correct
29	Correct	5 ms	11980 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	11980 KB	Output is correct
2	Correct	5 ms	11980 KB	Output is correct
3	Correct	6 ms	11980 KB	Output is correct
4	Correct	6 ms	11980 KB	Output is correct
5	Correct	6 ms	11980 KB	Output is correct
6	Correct	6 ms	11960 KB	Output is correct
7	Correct	6 ms	11948 KB	Output is correct
8	Correct	6 ms	11980 KB	Output is correct
9	Correct	7 ms	11924 KB	Output is correct
10	Correct	5 ms	11980 KB	Output is correct
11	Correct	6 ms	11980 KB	Output is correct
12	Correct	5 ms	11980 KB	Output is correct
13	Correct	6 ms	11980 KB	Output is correct
14	Correct	6 ms	11980 KB	Output is correct
15	Correct	6 ms	11944 KB	Output is correct
16	Correct	6 ms	11980 KB	Output is correct
17	Correct	6 ms	11980 KB	Output is correct
18	Correct	8 ms	12036 KB	Output is correct
19	Correct	9 ms	11980 KB	Output is correct
20	Correct	7 ms	12072 KB	Output is correct
21	Correct	5 ms	11980 KB	Output is correct
22	Correct	7 ms	11980 KB	Output is correct
23	Correct	6 ms	12092 KB	Output is correct
24	Correct	6 ms	11980 KB	Output is correct
25	Correct	6 ms	11980 KB	Output is correct
26	Correct	6 ms	11980 KB	Output is correct
27	Correct	6 ms	11980 KB	Output is correct
28	Correct	6 ms	12108 KB	Output is correct
29	Correct	5 ms	11980 KB	Output is correct
30	Correct	500 ms	70908 KB	Output is correct
31	Correct	479 ms	70976 KB	Output is correct
32	Correct	99 ms	23920 KB	Output is correct
33	Correct	518 ms	70996 KB	Output is correct
34	Correct	491 ms	71172 KB	Output is correct
35	Correct	493 ms	71108 KB	Output is correct
36	Correct	471 ms	70996 KB	Output is correct
37	Correct	426 ms	71020 KB	Output is correct
38	Correct	460 ms	70996 KB	Output is correct
39	Correct	507 ms	70892 KB	Output is correct
40	Correct	442 ms	70896 KB	Output is correct
41	Correct	455 ms	70984 KB	Output is correct
42	Correct	473 ms	70932 KB	Output is correct
43	Correct	451 ms	71020 KB	Output is correct

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	11972 KB	Output is correct
2	Correct	6 ms	11980 KB	Output is correct
3	Incorrect	6 ms	11980 KB	3rd lines differ - on the 1st token, expected: '5920', found: '5922'
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	11980 KB	Output is correct
2	Correct	5 ms	11980 KB	Output is correct
3	Correct	6 ms	11980 KB	Output is correct
4	Correct	6 ms	11980 KB	Output is correct
5	Correct	6 ms	11980 KB	Output is correct
6	Correct	6 ms	11960 KB	Output is correct
7	Correct	6 ms	11948 KB	Output is correct
8	Correct	6 ms	11980 KB	Output is correct
9	Correct	7 ms	11924 KB	Output is correct
10	Correct	5 ms	11980 KB	Output is correct
11	Correct	6 ms	11980 KB	Output is correct
12	Correct	5 ms	11980 KB	Output is correct
13	Correct	6 ms	11980 KB	Output is correct
14	Correct	6 ms	11980 KB	Output is correct
15	Correct	6 ms	11944 KB	Output is correct
16	Correct	6 ms	11980 KB	Output is correct
17	Correct	6 ms	11980 KB	Output is correct
18	Correct	8 ms	12036 KB	Output is correct
19	Correct	9 ms	11980 KB	Output is correct
20	Correct	7 ms	12072 KB	Output is correct
21	Correct	5 ms	11980 KB	Output is correct
22	Correct	7 ms	11980 KB	Output is correct
23	Correct	6 ms	12092 KB	Output is correct
24	Correct	6 ms	11980 KB	Output is correct
25	Correct	6 ms	11980 KB	Output is correct
26	Correct	6 ms	11980 KB	Output is correct
27	Correct	6 ms	11980 KB	Output is correct
28	Correct	6 ms	12108 KB	Output is correct
29	Correct	5 ms	11980 KB	Output is correct
30	Correct	500 ms	70908 KB	Output is correct
31	Correct	479 ms	70976 KB	Output is correct
32	Correct	99 ms	23920 KB	Output is correct
33	Correct	518 ms	70996 KB	Output is correct
34	Correct	491 ms	71172 KB	Output is correct
35	Correct	493 ms	71108 KB	Output is correct
36	Correct	471 ms	70996 KB	Output is correct
37	Correct	426 ms	71020 KB	Output is correct
38	Correct	460 ms	70996 KB	Output is correct
39	Correct	507 ms	70892 KB	Output is correct
40	Correct	442 ms	70896 KB	Output is correct
41	Correct	455 ms	70984 KB	Output is correct
42	Correct	473 ms	70932 KB	Output is correct
43	Correct	451 ms	71020 KB	Output is correct
44	Correct	7 ms	11972 KB	Output is correct
45	Correct	6 ms	11980 KB	Output is correct
46	Incorrect	6 ms	11980 KB	3rd lines differ - on the 1st token, expected: '5920', found: '5922'
47	Halted	0 ms	0 KB	-