#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];
pair<int, int> go1[1000001], go2[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;
// go1[i] = { before(i),1 }, go2[i] = { next(i),1 };
}
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;
go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
}
path = i;
}
if (in[path] < in[s] && check) {
Q.push({ len,{x, path} });
go1[path] = { x,len - 1 }, go2[x] = { path,len - 1 };
}
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++;
in[x]++;
if (x != y) in[y]++;
tx = x, num = 0;
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;
}
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 (go2[y].second) len += go2[y].second, y = go2[y].first;
}
if (in[y] < in[next(y)]) {
Q.push({ len,{tx,y} });
go1[y] = { tx,len - 1 }, go2[tx] = { y,len - 1 };
}
}
printf("%d", tot * 2);
}
Compilation message
route.cpp: In function 'int main()':
route.cpp:20: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:22:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &in[i]);
^
route.cpp:37:21: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (in[path] < in[s] && check) {
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
20704 KB |
Output is correct |
2 |
Correct |
0 ms |
20704 KB |
Output is correct |
3 |
Correct |
0 ms |
20704 KB |
Output is correct |
4 |
Correct |
0 ms |
20704 KB |
Output is correct |
5 |
Correct |
0 ms |
20704 KB |
Output is correct |
6 |
Correct |
0 ms |
20704 KB |
Output is correct |
7 |
Correct |
39 ms |
20704 KB |
Output is correct |
8 |
Correct |
56 ms |
20704 KB |
Output is correct |
9 |
Correct |
219 ms |
20704 KB |
Output is correct |
10 |
Correct |
16 ms |
20704 KB |
Output is correct |
11 |
Execution timed out |
2000 ms |
21940 KB |
Execution timed out |
12 |
Halted |
0 ms |
0 KB |
- |