답안 #40151 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40151	2018-01-28T14:35:28 Z	alenam0161	고대 책들 (IOI17_books)	C++14	12 / 100	1 ms	3000 KB

books

#include "books.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;
bool used[N];
vector<int> cycl,a;
long long ans;
void dfs(int v) {
	used[v] = true;
	cycl.push_back(v);
	ans += abs(a[v] - v);
	if (used[a[v]])return;
	dfs(a[v]);
}
void print(vector<int> v) {
	for (int to : v) {
		cout << to << " :";
	}
	cout << endl;
}
long long minimum_walk(std::vector<int> p, int s) {
	a = p;
	int n = p.size();
	vector<pair<long long,int>> ms;
	vector<vector<int>> art;
	int lst = n - 1;
	while (lst >= 0 && p[lst] == lst)lst--;
	for (int i = 0; i < n; ++i) {
		if (used[i])continue;
		ans = 0;
		cycl.clear();
		dfs(i);
		if (ans > 0) {
			ms.push_back({ ans,i });
			sort(cycl.begin(), cycl.end());
			art.push_back(cycl);
		}
	}
	while (ms.size() > 0 && ms.back().first == 0)ms.pop_back();
	if (ms.size() == 0)return 0ll;
	long long an = 0;
	for (int i = 0; i < ms.size(); ++i) {
		an += ms[i].first;// cout << ms[i].first << " " << ms[i].second << endl;
	}
	an += ms.back().second * 2;
	if (art[0].back() == lst) {
	//	print(art[0]);
		an -= (art.size()-1)*2;
	}
	return an;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ms.size(); ++i) {
                    ^

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3000 KB	Output is correct
2	Correct	0 ms	3000 KB	Output is correct
3	Correct	0 ms	3000 KB	Output is correct
4	Correct	0 ms	3000 KB	Output is correct
5	Correct	0 ms	3000 KB	Output is correct
6	Correct	0 ms	3000 KB	Output is correct
7	Correct	0 ms	3000 KB	Output is correct
8	Correct	0 ms	3000 KB	Output is correct
9	Correct	0 ms	3000 KB	Output is correct
10	Correct	0 ms	3000 KB	Output is correct
11	Correct	0 ms	3000 KB	Output is correct
12	Correct	0 ms	3000 KB	Output is correct
13	Correct	0 ms	3000 KB	Output is correct
14	Correct	0 ms	3000 KB	Output is correct
15	Correct	0 ms	3000 KB	Output is correct
16	Correct	0 ms	3000 KB	Output is correct
17	Correct	0 ms	3000 KB	Output is correct
18	Correct	0 ms	3000 KB	Output is correct
19	Incorrect	1 ms	3000 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3000 KB	Output is correct
2	Correct	0 ms	3000 KB	Output is correct
3	Correct	0 ms	3000 KB	Output is correct
4	Correct	0 ms	3000 KB	Output is correct
5	Correct	0 ms	3000 KB	Output is correct
6	Correct	0 ms	3000 KB	Output is correct
7	Correct	0 ms	3000 KB	Output is correct
8	Correct	0 ms	3000 KB	Output is correct
9	Correct	0 ms	3000 KB	Output is correct
10	Correct	0 ms	3000 KB	Output is correct
11	Correct	0 ms	3000 KB	Output is correct
12	Correct	0 ms	3000 KB	Output is correct
13	Correct	0 ms	3000 KB	Output is correct
14	Correct	0 ms	3000 KB	Output is correct
15	Correct	0 ms	3000 KB	Output is correct
16	Correct	0 ms	3000 KB	Output is correct
17	Correct	0 ms	3000 KB	Output is correct
18	Correct	0 ms	3000 KB	Output is correct
19	Incorrect	1 ms	3000 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3000 KB	Output is correct
2	Correct	0 ms	3000 KB	Output is correct
3	Correct	0 ms	3000 KB	Output is correct
4	Correct	0 ms	3000 KB	Output is correct
5	Correct	0 ms	3000 KB	Output is correct
6	Correct	0 ms	3000 KB	Output is correct
7	Correct	0 ms	3000 KB	Output is correct
8	Correct	0 ms	3000 KB	Output is correct
9	Correct	0 ms	3000 KB	Output is correct
10	Correct	0 ms	3000 KB	Output is correct
11	Correct	0 ms	3000 KB	Output is correct
12	Correct	0 ms	3000 KB	Output is correct
13	Correct	0 ms	3000 KB	Output is correct
14	Correct	0 ms	3000 KB	Output is correct
15	Correct	0 ms	3000 KB	Output is correct
16	Correct	0 ms	3000 KB	Output is correct
17	Correct	0 ms	3000 KB	Output is correct
18	Correct	0 ms	3000 KB	Output is correct
19	Incorrect	1 ms	3000 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338864'
20	Halted	0 ms	0 KB	-

답안 #40151

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0