# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
502254 | fabijan_cikac | Xylophone (JOI18_xylophone) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 100;
int n;
map<int, map<int, int> > m;
int a[N] = { 0 };
int sol[N];
vector<pair<int, int> > q;
void query(int x, int y){
//cout << x + 1 << ' ' << y + 1 << endl;
int z; cin >> z; m[x][y] = z; m[y][x] = z;
q.push_back({x, y});
}
bool dobro(int x, int y, int z, int c){
int a = min(x, min(y, z)); int b = max(x, max(y, z));
if (abs(a - b) == c)
return true;
return false;
}
bool check(){
for (int i = 0; i < q.size(); ++i){
bool b = false;
if (q[i].second - q[i].first == 2 && dobro(q[i].first, q[i].first + 1, q[i].first + 2, m[q[i].first][q[i].second]))
b = true;
if (q[i].second - q[i].first == 1 && max(sol[q[i].first], sol[q[i].second]) - min(sol[q[i].first], sol[q[i].second]) == m[q[i].first][q[i].second])
b = true;
if (!b) return false;
}
int x = 0;
while (sol[x] != 1)
++x;
int y = 0;
while (sol[y] != n)
++y;
if (x > y) return false;
return true;
}
bool construct(){
for (int i = 2; i < n; ++i){
bool b = false;
for (int j = -1; j <= 1; ++j){
if (j == 0) continue;
int x = a[i - 1] + j * m[i - 1][i];
if (dobro(a[i - 2], a[i - 1], x, m[i - 2][i])){
a[i] = x; b = true; break;
}
}
if (b == false) return false;
}
vector<pair<int, int> > v;
for (int i = 0; i < n; ++i)
v.push_back({a[i], i});
sort(v.begin(), v.end());
for (int i = 0; i < n; ++i)
sol[v[i].second] = i + 1;
if (!check())
return false;
return true;
}
void answer(int x, int y){
}
void solve(int n){
query(0, 1);
for (int i = 2; i < n; ++i){
query(i - 2, i); query(i - 1, i);
}
if (n == 2){
answer(1, 1); answer(2, 2);
}
else{
a[1] = m[0][1];
if (!construct()){
memset(a, 0, sizeof(a)); a[1] = -m[0][1];
construct();
}
for (int i = 0; i < n; ++i)
answer(i + 1, sol[i]);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}