Submission #37848

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
37848	2017-12-28T10:25:37 Z	14kg	Mountain Trek Route (IZhO12_route)	C++11	100 / 100	216 ms	23792 KB

route

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

using namespace std;
typedef pair<int, pair<int, int> > pip;
int n, m, in[N], S_sum;
bool cc[N];
pair<int, int> go1[N], go2[N];
//priority_queue<pip, vector<pip>, greater<pip> > Q;
set<pip> S;

void S_push(pip x) {
	set<pip>::iterator it;
	S.insert(x), S_sum += x.first;
	while (S.begin() != S.end() && S_sum > m) {
		it = S.end(), it--, S_sum -= it->first;
		S.erase(it);
	}
}

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

//	freopen("input.txt", "r", stdin);

	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) {
			S_push({ len,{ x, path } }), check = false;
			go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
		} path = i;
	}
	if (in[path] < in[s] && check) {
		S_push({ len,{ x, path } });
		go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
	}

	while (S.end() != S.begin()) {
	//	if(m%10000==0)printf("%d \n", m);
		temp = *S.begin(), S.erase(S.begin());
		if (m < temp.first) break;
		len = temp.first, x = temp.second.first, y = temp.second.second;
		
		num = min2(min2(in[before(x)] - in[x], in[next(y)] - in[y]), m / len);
		tot += num, m -= len*num, S_sum -= len*num;

		in[x]+=num;
		if (x != y) in[y] += num;

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

		ty = y, path = len;
		while (in[ty] == in[next(ty)]) {
			len++, ty = next(ty);
			if (go2[ty].second) len += go2[ty].second, ty = go2[ty].first;
		}
		go2[y] = { ty,len - path };

		if (in[ty] < in[next(ty)]) {
			S_push({ len,{ tx,ty } });
			go1[ty] = { tx,len - 1 }, go2[tx] = { ty,len - 1 };
		}
	} printf("%d", tot * 2);
	// getchar(), getchar();
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:37: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:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i]);
                      ^
route.cpp:52:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (in[path] < in[s] && check) {
                     ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	21680 KB	Output is correct
2	Correct	0 ms	21680 KB	Output is correct
3	Correct	0 ms	21680 KB	Output is correct
4	Correct	0 ms	21680 KB	Output is correct
5	Correct	0 ms	21680 KB	Output is correct
6	Correct	0 ms	21680 KB	Output is correct
7	Correct	0 ms	21680 KB	Output is correct
8	Correct	0 ms	21680 KB	Output is correct
9	Correct	0 ms	21680 KB	Output is correct
10	Correct	23 ms	21680 KB	Output is correct
11	Correct	19 ms	23792 KB	Output is correct
12	Correct	13 ms	21680 KB	Output is correct
13	Correct	189 ms	21680 KB	Output is correct
14	Correct	216 ms	21680 KB	Output is correct
15	Correct	159 ms	21680 KB	Output is correct
16	Correct	149 ms	21680 KB	Output is correct
17	Correct	176 ms	21680 KB	Output is correct
18	Correct	159 ms	21680 KB	Output is correct
19	Correct	169 ms	21680 KB	Output is correct
20	Correct	166 ms	21680 KB	Output is correct