| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1159902 | Der_Vlapos | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
map<pii, int> rem;
int req(int l, int r)
{
if (rem[{l, r}])
return rem[{l, r}];
return rem[{l, r}] = query(l + 1, r + 1);
}
void solve(int n)
{
int L = 0, R = n - 1;
while (R - L > 1)
{
int M = (L + R) >> 1;
if (req(0, M) == n - 1)
R = M;
else
L = M;
}
{
vector<int> a(n);
a[0] = 0;
a[1] = req(0, 1);
int p = 0;
for (int i = p + 2; i < n; ++i)
{
int v1 = req(i - 2, i);
int v2 = req(i - 1, i);
int mx = max(a[i - 2], a[i - 1]);
int mn = min(a[i - 2], a[i - 1]);
int d = mx - mn;
if (d == v1)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (v1 == v2)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (a[i - 1] == mn)
a[i] = a[i - 1] - v2;
else
a[i] = a[i - 1] + v2;
}
}
}
int mn = 0;
for (int i = 0; i < n; ++i)
mn = min(mn, a[i]);
for (int i = 0; i < n; ++i)
{
a[i] -= mn;
}
bool good = true;
vector<int> pos(n);
for (int i = 0; i < n; ++i)
{
if (0 <= a[i] and a[i] < n)
{
}
else
{
good = false;
break;
}
pos[a[i]] = i;
}
if (good and pos[0] < pos[n - 1])
for (int i = 1; i <= n; i++)
answer(i, a[i - 1] + 1);
}
{
vector<int> a(n);
a[0] = 0;
a[1] = -req(0, 1);
int p = 0;
for (int i = p + 2; i < n; ++i)
{
int v1 = req(i - 2, i);
int v2 = req(i - 1, i);
int mx = max(a[i - 2], a[i - 1]);
int mn = min(a[i - 2], a[i - 1]);
int d = mx - mn;
if (d == v1)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (v1 == v2)
{
if (a[i - 1] == mn)
a[i] = a[i - 1] + v2;
else
a[i] = a[i - 1] - v2;
}
else
{
if (a[i - 1] == mn)
a[i] = a[i - 1] - v2;
else
a[i] = a[i - 1] + v2;
}
}
}
int mn = 0;
for (int i = 0; i < n; ++i)
mn = min(mn, a[i]);
for (int i = 0; i < n; ++i)
a[i] -= mn;
bool good = true;
vector<int> pos(n);
for (int i = 0; i < n; ++i)
{
if (0 <= a[i] and a[i] < n)
{
}
else
{
good = false;
break;
}
pos[a[i]] = i;
}
if (good and pos[0] < pos[n - 1])
for (int i = 1; i <= n; i++)
answer(i, a[i - 1] + 1);
}
}
#include <cstdio>
#include <cstdlib>
#include "xylophone.h"
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()
{
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);
}