답안 #37735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37735	2017-12-27T11:59:20 Z	14kg	등산 경로 (IZhO12_route)	C++11	0 / 100	2000 ms	6312 KB

route

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define next(x) (x==n?1:x+1)
#define before(x) (x==1?n:x-1)

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, in[1000001];
priority_queue<pip, vector<pip>, greater<pip> > Q;

int main() {
	int s, num = -1;
	int path, x, y, len, tot = 0, tx;
	bool check;

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in[i]);
		if (num < in[i]) num = in[i], s = i;
	}

	path = s, len = 0, check = false;;
	for (int i = next(s); i != s; i = next(i)) {
		if (in[path] > in[i]) x = i, len = 1, check = true;
		if (in[path] == in[i]) len++;
		if (in[path] < in[i] && check) Q.push({ len,{x, path} }), check = false;
		path = i;
	}
	if (in[path] < in[s] && check) Q.push({ len,{x, path} });

	while ((!Q.empty()) && Q.top().first <= m) {
		len = Q.top().first, x = Q.top().second.first, y = Q.top().second.second;
		Q.pop(), m -= len ,tot++;

		tx = x;
		for (int i = 1; i <= len; i++) in[tx]++, tx = next(tx);

		tx = x, num = 0;
		while (in[before(tx)] == in[tx]) {
			num++, tx = before(tx), len++;
			if (num > n) break;
		}
		if (in[before(tx)] == in[tx]) break;
		if (in[before(tx)] < in[tx]) continue;

		while (in[y] == in[next(y)]) len++, y = next(y);

		if (in[y] < in[next(y)]) Q.push({ len,{tx,y} });
	}
	printf("%d", tot * 2);
	//getchar(), getchar();
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
route.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i]);
                      ^
route.cpp:32:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (in[path] < in[s] && check) Q.push({ len,{x, path} });
                     ^

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5076 KB	Output is correct
2	Correct	0 ms	5076 KB	Output is correct
3	Correct	0 ms	5076 KB	Output is correct
4	Correct	0 ms	5076 KB	Output is correct
5	Correct	0 ms	5076 KB	Output is correct
6	Correct	0 ms	5076 KB	Output is correct
7	Correct	36 ms	5076 KB	Output is correct
8	Correct	66 ms	5076 KB	Output is correct
9	Correct	363 ms	5076 KB	Output is correct
10	Correct	223 ms	5076 KB	Output is correct
11	Execution timed out	2000 ms	6312 KB	Execution timed out
12	Halted	0 ms	0 KB	-