답안 #1049667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1049667 2024-08-09T03:45:05 Z Gromp15 고대 책들 (IOI17_books) C++17
70 / 100
1391 ms 370572 KB
#include <bits/stdc++.h>
#define ll long long
#include "books.h"
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ar array
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct seg {
	int N; vector<vector<ar<int, 2>>> adj;
	seg(int n) : N(1<<(__lg(n)+1)), adj(2*N) {
		for (int i = 2; i < 2*N; i++) adj[i].push_back({i >> 1, 0});
	}
	void add_edge(int x, int y) {
		adj[x+N].push_back({y+N, 1});
	}
	void add_edge(int node, int nl, int nr, int ql, int qr, int x) { // l and r go to x
		if (ql > nr || qr < nl) return;
		if (ql <= nl && nr <= qr) {
			adj[node].push_back({x + N, 0});
			return;
		}
		int mid = (nl+nr)/2;
		add_edge(node * 2, nl, mid, ql, qr, x);
		add_edge(node * 2 + 1, mid + 1, nr, ql, qr, x);
	}
	void bfs(vector<int>& dist, vector<int> nodes) {
		vector<int> dist2(2 * N, 2e9);
		for (int i = 0; i < sz(dist); i++) dist2[i + N] = dist[i];
		deque<int> q;
		vector<int> idx(sz(dist));
		iota(all(idx), 0);
		sort(all(idx), [&](int x, int y) { return dist[x] < dist[y]; });
		int on = 1;
		q.emplace_back(idx[0] + N);
		while (q.size()) {
			int v = q[0]; q.pop_front();
			for (auto [u, w] : adj[v]) { 
				if (ckmin(dist2[u], dist2[v] + w)) { 
					if (!w) q.emplace_front(u);
					else q.emplace_back(u);
				}
			}
			if (on < sz(dist) && (q.empty() || dist[idx[on]] <= dist2[q[0]])) {
				q.emplace_front(idx[on++] + N);
			}
		}
		assert(on == sz(dist));
		for (int i = 0; i < sz(dist); i++) dist[i] = dist2[i + N];
	}
};

long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	{
		int l = s, r = s;
		bool f = 0;
		for (int i = s; i >= 0; i--) if (i != p[i]) l = i, f = 1;
		for (int i = s; i < n; i++) if (i != p[i]) r = i, f = 1;
		if (!f) {
			return 0;
		}
		p = vector<int>(p.begin() + l, p.begin() + r + 1);
		n = r - l + 1;
	}
	seg st(n);
	for (int i = 0; i < n; i++) {
		if (i) st.add_edge(i, i-1);
		if (i+1 < n) st.add_edge(i, i+1);
	}
	vector<bool> vis(n);
	ll ans = 0;
	for (int i = 0; i < n; i++) if (!vis[i]) {
		int L = i, R = i, tmp = i;
		vector<int> pth;
		while (!vis[tmp]) { 
			ans += abs(tmp - p[tmp]);
			ckmax(R, tmp), vis[tmp] = 1;
			pth.emplace_back(tmp);
			tmp = p[tmp];
		}
		for (int v : pth) st.add_edge(1, 0, st.N-1, L, R, v);
	}
	vector<int> d1(n, 1e9), d2(n, 1e9);
	d1[0] = 0, d2[n-1] = 0;
	st.bfs(d1, {0});
	st.bfs(d2, {n-1});
	vector<int> d3(n);
	for (int i = 0; i < n; i++) d3[i] = d1[i] + d2[i];
	vector<int> tot(n);
	iota(all(tot), 0);
	st.bfs(d3, tot);
	return ans + 2 * d3[s];
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1193 ms 302008 KB Output is correct
31 Correct 1239 ms 370572 KB Output is correct
32 Correct 55 ms 8016 KB Output is correct
33 Correct 587 ms 189444 KB Output is correct
34 Correct 584 ms 189444 KB Output is correct
35 Correct 629 ms 197540 KB Output is correct
36 Correct 777 ms 219108 KB Output is correct
37 Correct 763 ms 261896 KB Output is correct
38 Correct 784 ms 284064 KB Output is correct
39 Correct 801 ms 284384 KB Output is correct
40 Correct 794 ms 304824 KB Output is correct
41 Correct 1020 ms 319376 KB Output is correct
42 Correct 964 ms 361144 KB Output is correct
43 Correct 1391 ms 214916 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1193 ms 302008 KB Output is correct
31 Correct 1239 ms 370572 KB Output is correct
32 Correct 55 ms 8016 KB Output is correct
33 Correct 587 ms 189444 KB Output is correct
34 Correct 584 ms 189444 KB Output is correct
35 Correct 629 ms 197540 KB Output is correct
36 Correct 777 ms 219108 KB Output is correct
37 Correct 763 ms 261896 KB Output is correct
38 Correct 784 ms 284064 KB Output is correct
39 Correct 801 ms 284384 KB Output is correct
40 Correct 794 ms 304824 KB Output is correct
41 Correct 1020 ms 319376 KB Output is correct
42 Correct 964 ms 361144 KB Output is correct
43 Correct 1391 ms 214916 KB Output is correct
44 Correct 1 ms 600 KB Output is correct
45 Correct 1 ms 604 KB Output is correct
46 Correct 1 ms 604 KB Output is correct
47 Correct 1 ms 604 KB Output is correct
48 Correct 0 ms 604 KB Output is correct
49 Correct 1 ms 600 KB Output is correct
50 Correct 1 ms 600 KB Output is correct
51 Correct 1 ms 604 KB Output is correct
52 Correct 1 ms 604 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 604 KB Output is correct
55 Correct 1 ms 604 KB Output is correct
56 Correct 1 ms 604 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 1 ms 604 KB Output is correct
59 Correct 1 ms 604 KB Output is correct
60 Correct 1 ms 604 KB Output is correct
61 Correct 1 ms 604 KB Output is correct
62 Correct 1 ms 604 KB Output is correct
63 Correct 1 ms 604 KB Output is correct
64 Correct 936 ms 189672 KB Output is correct
65 Incorrect 750 ms 285192 KB 3rd lines differ - on the 1st token, expected: '7226436', found: '8929100'
66 Halted 0 ms 0 KB -