| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 358378 | Lam_lai_cuoc_doi | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include <set>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;
const int N = 5e3 + 2;
int n;
int a[N][N];
set<pair<int, int>> s[N];
/*int query(int u, int v)
{
cout << u << " " << v << "\n";
int a;
cin >> a;
return a;
}
void answer(int u, int v)
{
cout << u << ": " << v << "\n";
}*/
void solve(int n)
{
for (int i = 1; i < n; ++i)
{
a[i][i + 1] = query(i, i + 1);
s[a[i][i + 1]].insert({i, i + 1});
}
for (int i = 1; i < n - 1; ++i)
{
int v = query(i, i + 2);
if (v == a[i][i + 1] + a[i + 1][i + 2])
{
a[i][i + 2] = v;
s[v].insert({i, i + 2});
}
else
{
if (v == a[i][i + 1])
{
a[i][i + 2] = v - a[i + 1][i + 2];
s[a[i][i + 2]].insert({i, i + 2});
}
else
{
a[i][i + 2] = v - a[i][i + 1];
s[a[i][i + 2]].insert({i, i + 2});
}
}
}
for (int i = 3; i < n; ++i)
{
int sum(0);
for (int j = 1; j < i - 1; ++j)
sum += a[j][j + 1];
for (int j = 1; j <= n - i; ++j)
{
sum -= a[j - 1][j];
sum += a[j + i - 1][j + i];
int v = query(j, i + j);
if (v == sum)
{
a[j][i + j] = v;
s[v].insert({j, i + j});
}
else
{
auto t = s[v].lower_bound({j, 0});
if (t->first == j)
{
a[j][i + j] = v - a[t->second][j + i];
s[a[j][i + j]].insert({j, i + j});
}
else if (t->second == j + i)
{
a[j][i + j] = v - a[j][t->first];
s[a[j][j + i]].insert({j, j + i});
}
else
{
a[j][i + j] = v - min(a[j][t->first] + a[t->second][j + i], a[j][t->second] + a[t->first][j + i]);
s[a[j][j + i]].insert({j, j + i});
}
}
}
}
int pos;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (a[i][j] == n - 1)
{
pos = i;
goto done;
}
done:;
/*for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
cout << a[min(i, j)][max(i, j)] << " ";
cout << "\n";
}*/
for (int i = 1; i <= n; ++i)
{
if (i == pos)
answer(i, 1);
else
answer(i, 1 + (i < pos ? a[i][pos] : a[pos][i]));
}
for (int i = 1; i <= n; ++i)
s[i].clear();
}
int32_t main()
{
//ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve(5);
}