#include <bits/stdc++.h>
//#define DEBUG
#ifndef DEBUG
#include "xylophone.h"
#endif
using namespace std;
#ifdef DEBUG
int query(int s, int t);
void answer(int i, int a);
#endif
map<int, int> mp[10005];
int v[10005];
int myquery(int st, int dr)
{
if(st == dr) return 0;
if(st > dr) return -1;
if(mp[st].count(dr)) return mp[st][dr];
mp[st][dr] = query(st, dr);
return mp[st][dr];
}
bool valid(int x, int y, int z, int dxz)
{
int mx = max({x, y, z});
int mn = min({x, y, z});
return (mx - mn) == dxz;
}
void solve(int N)
{
for(int i = 1; i <= N; i++) mp[i].clear();
for(int i = 1; i <= N; i++) v[i] = 0;
int st = 1, dr = N;
int p = 2, u = N;
while(p <= u)
{
int mij = p + (u - p) / 2;
if( myquery(1, mij) == N - 1 )
dr = mij, u = mij - 1;
else
p = mij + 1;
}
p = 1, u = dr - 1;
while(p <= u)
{
int mij = p + (u - p) / 2;
if( myquery(mij, dr) == N - 1 )
st = mij, p = mij + 1;
else
u = mij - 1;
}
answer(st, 1); v[st] = 1;
answer(dr, N); v[dr] = N;
if(st > 1)
{
int d = myquery(st - 1, st);
answer(st - 1, d + 1); v[st - 1] = d + 1;
for(int i = st - 2; i >= 1; i--)
{
int x = v[i + 1], y = v[i + 2];
int dx = myquery(i, i + 1);
int dy = myquery(i, i + 2);
if(valid(x - dx, x, y, dy))
{
answer(i, x - dx);
v[i] = x - dx;
}
else
{
answer(i, x + dx);
v[i] = x + dx;
}
}
}
if(st + 1 < dr)
{
int d = myquery(st, st + 1);
answer(st + 1, d + 1); v[st + 1] = d + 1;
for(int i = st + 2; i < dr; i++)
{
int x = v[i - 1], y = v[i - 2];
int dx = myquery(i - 1, i);
int dy = myquery(i - 2, i);
if(valid(x - dx, x, y, dy))
{
answer(i, x - dx);
v[i] = x - dx;
}
else
{
answer(i, x + dx);
v[i] = x + dx;
}
}
}
if(dr < N)
{
int d = myquery(dr, dr + 1);
answer(dr + 1, N - d); v[dr + 1] = N - d;
for(int i = dr + 2; i <= N; i++)
{
int x = v[i - 1], y = v[i - 2];
int dx = myquery(i - 1, i);
int dy = myquery(i - 2, i);
if(valid(x - dx, x, y, dy))
{
answer(i, x - dx);
v[i] = x - dx;
}
else
{
answer(i, x + dx);
v[i] = x + dx;
}
}
}
}
#ifdef DEBUG
static const int N_MAX = 5000;
static const int Q_MAX = 10000;
static int N;
static int A[N_MAX];
static bool used[N_MAX];
static int query_c;
static int answer_c;
int query(int s, int t) {
if(query_c >= Q_MAX) {
printf("Wrong Answer\n");
exit(0);
}
query_c++;
if(!(1 <= s && s <= t && t <= N)) {
printf("Wrong Answer\n");
exit(0);
}
int mx = 0, mn = N + 1;
for(int i = s - 1; i < t; i++) {
if(mx < A[i]) {
mx = A[i];
}
if(mn > A[i]) {
mn = A[i];
}
}
return mx - mn;
}
void answer(int i, int a) {
answer_c++;
if(!(1 <= i && i <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(!(1 <= a && a <= N)) {
printf("Wrong Answer\n");
exit(0);
}
if(used[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
if(a != A[i - 1]) {
printf("Wrong Answer\n");
exit(0);
}
used[i - 1] = true;
}
int main() {
freopen("1.in", "r", stdin);
query_c = 0;
answer_c = 0;
if(scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for(int i = 0; i < N; i++) {
if(scanf("%d", A + i) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
used[i] = false;
}
solve(N);
if(!(answer_c == N)) {
printf("Wrong Answer\n");
exit(0);
}
printf("Accepted : %d\n", query_c);
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
2 ms |
836 KB |
Output is correct |
3 |
Correct |
3 ms |
884 KB |
Output is correct |
4 |
Correct |
4 ms |
884 KB |
Output is correct |
5 |
Correct |
4 ms |
920 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Correct |
4 ms |
976 KB |
Output is correct |
8 |
Correct |
4 ms |
976 KB |
Output is correct |
9 |
Correct |
4 ms |
976 KB |
Output is correct |
10 |
Correct |
3 ms |
1136 KB |
Output is correct |
11 |
Correct |
3 ms |
1136 KB |
Output is correct |
12 |
Correct |
3 ms |
1180 KB |
Output is correct |
13 |
Correct |
4 ms |
1180 KB |
Output is correct |
14 |
Correct |
4 ms |
1180 KB |
Output is correct |
15 |
Correct |
3 ms |
1180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
2 ms |
836 KB |
Output is correct |
3 |
Correct |
3 ms |
884 KB |
Output is correct |
4 |
Correct |
4 ms |
884 KB |
Output is correct |
5 |
Correct |
4 ms |
920 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Correct |
4 ms |
976 KB |
Output is correct |
8 |
Correct |
4 ms |
976 KB |
Output is correct |
9 |
Correct |
4 ms |
976 KB |
Output is correct |
10 |
Correct |
3 ms |
1136 KB |
Output is correct |
11 |
Correct |
3 ms |
1136 KB |
Output is correct |
12 |
Correct |
3 ms |
1180 KB |
Output is correct |
13 |
Correct |
4 ms |
1180 KB |
Output is correct |
14 |
Correct |
4 ms |
1180 KB |
Output is correct |
15 |
Correct |
3 ms |
1180 KB |
Output is correct |
16 |
Correct |
6 ms |
1180 KB |
Output is correct |
17 |
Correct |
11 ms |
1180 KB |
Output is correct |
18 |
Correct |
21 ms |
1180 KB |
Output is correct |
19 |
Correct |
20 ms |
1180 KB |
Output is correct |
20 |
Correct |
12 ms |
1192 KB |
Output is correct |
21 |
Correct |
20 ms |
1192 KB |
Output is correct |
22 |
Correct |
18 ms |
1228 KB |
Output is correct |
23 |
Correct |
17 ms |
1228 KB |
Output is correct |
24 |
Correct |
18 ms |
1228 KB |
Output is correct |
25 |
Correct |
19 ms |
1228 KB |
Output is correct |
26 |
Correct |
13 ms |
1228 KB |
Output is correct |
27 |
Correct |
18 ms |
1228 KB |
Output is correct |
28 |
Correct |
19 ms |
1228 KB |
Output is correct |
29 |
Correct |
20 ms |
1228 KB |
Output is correct |
30 |
Correct |
18 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
760 KB |
Output is correct |
2 |
Correct |
2 ms |
836 KB |
Output is correct |
3 |
Correct |
3 ms |
884 KB |
Output is correct |
4 |
Correct |
4 ms |
884 KB |
Output is correct |
5 |
Correct |
4 ms |
920 KB |
Output is correct |
6 |
Correct |
3 ms |
976 KB |
Output is correct |
7 |
Correct |
4 ms |
976 KB |
Output is correct |
8 |
Correct |
4 ms |
976 KB |
Output is correct |
9 |
Correct |
4 ms |
976 KB |
Output is correct |
10 |
Correct |
3 ms |
1136 KB |
Output is correct |
11 |
Correct |
3 ms |
1136 KB |
Output is correct |
12 |
Correct |
3 ms |
1180 KB |
Output is correct |
13 |
Correct |
4 ms |
1180 KB |
Output is correct |
14 |
Correct |
4 ms |
1180 KB |
Output is correct |
15 |
Correct |
3 ms |
1180 KB |
Output is correct |
16 |
Correct |
6 ms |
1180 KB |
Output is correct |
17 |
Correct |
11 ms |
1180 KB |
Output is correct |
18 |
Correct |
21 ms |
1180 KB |
Output is correct |
19 |
Correct |
20 ms |
1180 KB |
Output is correct |
20 |
Correct |
12 ms |
1192 KB |
Output is correct |
21 |
Correct |
20 ms |
1192 KB |
Output is correct |
22 |
Correct |
18 ms |
1228 KB |
Output is correct |
23 |
Correct |
17 ms |
1228 KB |
Output is correct |
24 |
Correct |
18 ms |
1228 KB |
Output is correct |
25 |
Correct |
19 ms |
1228 KB |
Output is correct |
26 |
Correct |
13 ms |
1228 KB |
Output is correct |
27 |
Correct |
18 ms |
1228 KB |
Output is correct |
28 |
Correct |
19 ms |
1228 KB |
Output is correct |
29 |
Correct |
20 ms |
1228 KB |
Output is correct |
30 |
Correct |
18 ms |
1228 KB |
Output is correct |
31 |
Correct |
41 ms |
1364 KB |
Output is correct |
32 |
Correct |
50 ms |
1364 KB |
Output is correct |
33 |
Correct |
69 ms |
1484 KB |
Output is correct |
34 |
Incorrect |
85 ms |
1620 KB |
Wrong Answer [2] |
35 |
Halted |
0 ms |
0 KB |
- |