oj.uz

답안 #669948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669948 2022-12-07T16:25:20 Z flappybird 고대 책들 (IOI17_books) C++17
50 / 100
 543 ms 112428 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define MAX 1010101
typedef pair<int, int> pii;
typedef long long ll;

int p[MAX];
ll ans = 0;
int N;
vector<vector<int>> cyc;
int cycnt;
int vis[MAX];
int chk[MAX];
int prt[MAX];
int lv[MAX];
int rv[MAX];
vector<int> adj[MAX];
vector<int> lst;
int s;
int pp[MAX];
int find(int x) {
	if (!~x) return -1;
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}
void uni(int x, int y) {
	x = find(x);
	y = find(y);
	pp[x] = y;
}
void dfs(int x) {
	lst.push_back(x);
	for (auto v : adj[x]) if (lv[v] <= s && s <= rv[v]) dfs(v);
}
long long minimum_walk(std::vector<int> p, int _s) {
	s = _s;
	N = p.size();
	int i;
	for (i = 0; i < N; i++) if (i != p[i]) break;
	int er = i;
	if (i == N) return 0;
	int fcnt = 0;
	for (; i < N; i++) p[fcnt++] = p[i] - er;
	s -= er;
	if (s < 0) ans += 2ll * (-s), s = 0;
	N = fcnt;
	p.resize(N);
	while ((p.back() + 1) == (int)p.size()) p.pop_back();
	N = p.size();
	if (s >= N) ans += 2ll * (s - N + 1), s = N - 1;
	for (i = 0; i < N; i++) ans += abs(p[i] - i);
	for (i = 0; i < N; i++) {
		if (vis[i]) continue;
		vector<int> vlist;
		int v = i;
		while (!vis[v]) {
			vis[v] = 1;
			vlist.push_back(v);
			v = p[v];
		}
		cycnt++;
		cyc.push_back(vlist);
	}
	vector<pair<pii, int>> vpi;
	int X = cyc.size();
	for (i = 0; i < X; i++) pp[i] = i;
	for (auto& v : cyc) {
		sort(v.begin(), v.end());
		vpi.emplace_back(pii(v[0], v.back()), 0);
	}
	i = 0;
	for (auto& [_, x] : vpi) x = i++;
	sort(vpi.begin(), vpi.end());
	vector<pair<pii, int>> stk;
	for (i = 0; i < vpi.size(); i++) {
		while (stk.size() && stk.back().first.second < vpi[i].first.first) stk.pop_back();
		vector<int> er;
		int t = -1;
		while (stk.size() && vpi[i].first.first <= stk.back().first.second && stk.back().first.second <= vpi[i].first.second) {
			er.push_back(stk.back().second);
			stk.pop_back();
		}
		if (er.size()) {
			t = er.back();
			er.pop_back();
			er.push_back(i);
			for (auto x : er) {
				chk[x] = 1;
				if (cyc[t].size() < cyc[x].size()) swap(cyc[t], cyc[x]);
				for (auto v : cyc[x]) cyc[t].push_back(v);
				uni(x, t);
			}
			stk.emplace_back(pii(cyc[t][0], vpi[i].first.second), t);
		}
		else {
			if (stk.empty()) prt[i] = -1;
			else prt[i] = stk.back().second;
			stk.push_back(vpi[i]);
		}
	}
	vector<int> all;
	for (i = 0; i < X; i++) {
		if (!chk[i]) {
			sort(cyc[i].begin(), cyc[i].end());
			lv[i] = cyc[i][0];
			rv[i] = cyc[i].back();
			prt[i] = find(prt[i]);
			if (~prt[i]) adj[prt[i]].push_back(i);
		}
	}
	for (i = 0; i < cyc.size(); i++) if (!~prt[i]) all.push_back(i);
	for (i = 1; i < all.size(); i++) ans += 2ll * (lv[all[i]] - rv[all[i - 1]]);
	int rt = -1;
	for (auto v : all) {
		if (lv[v] <= s && s <= rv[v]) {
			rt = v;
			break;
		}
	}
	dfs(rt);
	set<int> st;
	for (auto v : cyc[lst[0]]) st.insert(v);
	for (i = 1; i < lst.size(); i++) {
		auto ind = st.lower_bound(lv[lst[i]]);
		int c;
		if (ind == st.end()) c = 0;
		else if (*ind <= rv[lst[i]]) c = 1;
		else c = 0;
		if (!c) {
			ind = st.lower_bound(lv[lst[i]]);
			int mn = 2e9;
			if (ind != st.begin()) {
				ind--;
				mn = min(mn, abs(*ind - lv[lst[i]]));
			}
			ind = st.upper_bound(rv[lst[i]]);
			if (ind != st.end()) mn = min(mn, abs(*ind - rv[lst[i]]));
			ans += 2ll * mn;
		}
		for (auto v : cyc[lst[i]]) st.insert(v);
	}
	return ans;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (i = 0; i < vpi.size(); i++) {
      |              ~~^~~~~~~~~~~~
books.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (i = 0; i < cyc.size(); i++) if (!~prt[i]) all.push_back(i);
      |              ~~^~~~~~~~~~~~
books.cpp:113:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for (i = 1; i < all.size(); i++) ans += 2ll * (lv[all[i]] - rv[all[i - 1]]);
      |              ~~^~~~~~~~~~~~
books.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for (i = 1; i < lst.size(); i++) {
      |              ~~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24020 KB Output is correct
2 Correct 12 ms 24020 KB Output is correct
3 Correct 12 ms 24020 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 12 ms 24020 KB Output is correct
7 Correct 12 ms 24020 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 12 ms 24020 KB Output is correct
11 Correct 12 ms 24020 KB Output is correct
12 Correct 12 ms 24020 KB Output is correct
13 Correct 12 ms 24020 KB Output is correct
14 Correct 12 ms 24020 KB Output is correct
15 Correct 12 ms 24020 KB Output is correct
16 Correct 12 ms 24020 KB Output is correct
17 Correct 12 ms 24020 KB Output is correct
18 Correct 13 ms 24020 KB Output is correct
19 Correct 12 ms 24020 KB Output is correct
20 Correct 12 ms 24020 KB Output is correct
21 Correct 12 ms 24020 KB Output is correct
22 Correct 12 ms 24148 KB Output is correct
23 Correct 12 ms 24148 KB Output is correct
24 Correct 13 ms 24020 KB Output is correct
25 Correct 12 ms 24020 KB Output is correct
26 Correct 12 ms 24020 KB Output is correct
27 Correct 12 ms 24020 KB Output is correct
28 Correct 13 ms 24020 KB Output is correct
29 Correct 14 ms 24148 KB Output is correct
30 Correct 543 ms 86964 KB Output is correct
31 Correct 449 ms 77304 KB Output is correct
32 Correct 90 ms 31792 KB Output is correct
33 Correct 234 ms 110340 KB Output is correct
34 Correct 228 ms 110408 KB Output is correct
35 Correct 224 ms 97716 KB Output is correct
36 Correct 179 ms 63856 KB Output is correct
37 Correct 160 ms 44264 KB Output is correct
38 Correct 165 ms 42032 KB Output is correct
39 Correct 166 ms 42036 KB Output is correct
40 Correct 188 ms 41796 KB Output is correct
41 Correct 263 ms 51884 KB Output is correct
42 Correct 207 ms 41896 KB Output is correct
43 Correct 243 ms 112428 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 24020 KB Output is correct
2 Correct 12 ms 24020 KB Output is correct
3 Correct 12 ms 24020 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 12 ms 24020 KB Output is correct
7 Correct 12 ms 24020 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 12 ms 24020 KB Output is correct
10 Correct 12 ms 24020 KB Output is correct
11 Correct 12 ms 24020 KB Output is correct
12 Correct 12 ms 24020 KB Output is correct
13 Correct 12 ms 24020 KB Output is correct
14 Correct 12 ms 24020 KB Output is correct
15 Correct 12 ms 24020 KB Output is correct
16 Correct 12 ms 24020 KB Output is correct
17 Correct 12 ms 24020 KB Output is correct
18 Correct 13 ms 24020 KB Output is correct
19 Correct 12 ms 24020 KB Output is correct
20 Correct 12 ms 24020 KB Output is correct
21 Correct 12 ms 24020 KB Output is correct
22 Correct 12 ms 24148 KB Output is correct
23 Correct 12 ms 24148 KB Output is correct
24 Correct 13 ms 24020 KB Output is correct
25 Correct 12 ms 24020 KB Output is correct
26 Correct 12 ms 24020 KB Output is correct
27 Correct 12 ms 24020 KB Output is correct
28 Correct 13 ms 24020 KB Output is correct
29 Correct 14 ms 24148 KB Output is correct
30 Correct 543 ms 86964 KB Output is correct
31 Correct 449 ms 77304 KB Output is correct
32 Correct 90 ms 31792 KB Output is correct
33 Correct 234 ms 110340 KB Output is correct
34 Correct 228 ms 110408 KB Output is correct
35 Correct 224 ms 97716 KB Output is correct
36 Correct 179 ms 63856 KB Output is correct
37 Correct 160 ms 44264 KB Output is correct
38 Correct 165 ms 42032 KB Output is correct
39 Correct 166 ms 42036 KB Output is correct
40 Correct 188 ms 41796 KB Output is correct
41 Correct 263 ms 51884 KB Output is correct
42 Correct 207 ms 41896 KB Output is correct
43 Correct 243 ms 112428 KB Output is correct
44 Incorrect 13 ms 24148 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3586'
45 Halted 0 ms 0 KB -