| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288002 | am_aadvik | Xylophone (JOI18_xylophone) | C++20 | 0 ms | 0 KiB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include<map>
#include <cassert>
#include<set>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
#define SUBMIT 1
#ifndef SUBMIT
#include <cstdio>
#include <cstdlib>
void solve(int N);
int query(int s, int t);
void answer(int i, int a);
vector<int> oa;
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() {
int n = 50;
for (int tc = 0; tc < 30; ++tc) {
for (int i = 0; i < n; ++i) {
oa.push_back(i + 1);
}
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
shuffle(oa.begin(), oa.end(), default_random_engine(seed));
query_c = 0;
answer_c = 0;
N = n;
for (int i = 0; i < N; i++) {
A[i] = oa[i];
used[i] = false;
}
solve(N);
if (!(answer_c == N)) {
printf("Wrong Answer\n");
exit(0);
}
printf("Accepted : %d\n", query_c);
}
}
#endif
vector<int> a1, a2;
int findc(int a, int b, int i) {
int c = 0;
if (a2[i] == a1[i]) {
//mn, mx = (a,b)
//min(a, b) < c < max(a, b)
if (a < b) //a < c < b
c = b - a1[i + 1];
else //b < c < a
c = b + a1[i + 1];
}
else if (a2[i] == a1[i + 1]) {
//mn, mx = (b, c)
//min(b, c) < a < max(b, c)
if (b > a) //c < a < b
c = b - a1[i + 1];
else //b < a < c
c = b + a1[i + 1];
}
else {
//mn, mx = (a, c)
//min(a, c) < b < max(a, c)
if (a < b) //a < b < c
c = b + a1[i + 1];
else //c < b < a
c = b - a1[i + 1];
}
return c;
}
void solve(int n) {
a1.resize(n + 1), a2.resize(n + 1);
int cnt = 0;
set<vector<int>> res;
for (int i = 1; i < n; ++i)
a1[i] = query(i, i + 1);
for (int i = 1; i < (n - 1); ++i)
a2[i] = query(i, i + 2);
for (int a = 1; a <= n; ++a)
for (auto b : { a + a1[1], a - a1[1] }) {
vector<int> cres = { a, b };
int i = 1, ca = a, cb = b;
while (cres.size() != n) {
int c = findc(ca, cb, i);
ca = cb, cb = c, ++i;
cres.push_back(c);
}
vector<int> freq(n + 1);
freq[0] = 1;
for (auto x : cres)
if ((x >= 0) && (x <= n))
++freq[x];
bool found1 = 0, ok = 1;
for (int i = 0; i < n; ++i)
if (cres[i] == 1) found1 = 1;
else if (cres[i] == n) if (!found1) ok = 0;
if ((*min_element(freq.begin(), freq.end()) * *max_element(freq.begin(), freq.end()) * ok) == 1)
res.insert(cres), ++cnt;
}
#ifndef SUBMIT
assert(cnt <= 5);
cout << "Valid: " << cnt << " ";
#endif
while (res.size() > 1) {
auto x = *res.begin();
auto y = *res.rbegin();
if (x == y) continue;
for (int i = 0; i < n; ++i) {
int mx1 = x[i], mn1 = x[i];
int mx2 = y[i], mn2 = y[i];
for (int j = i + 1; j < n; ++j) {
mx1 = max(mx1, x[j]), mn1 = min(mn1, x[j]);
mx2 = max(mx2, y[j]), mn2 = min(mn2, y[j]);
if ((mx1 - mn1) != (mx2 - mn2)) {
int r = query(i + 1, j + 1);
if ((mx1 - mn1) != r) res.erase(x);
if ((mx2 - mn2) != r) res.erase(y);
break;
}
}
}
}
vector<int> ans = *res.begin();
for (int i = 1; i <= n; ++i) answer(i, ans[i - 1]);
}