# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
135004 | 2019-07-23T14:05:01 Z | osaaateiasavtnl | Xylophone (JOI18_xylophone) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> const int N = 5001; int ans[N]; int mem[2][N]; bool t[N], r[N]; int cnt[N]; bool check(int n) { for (int i = 1; i <= n; ++i) { if (ans[i] < 1 || ans[i] > n) return 0; } for (int i = 1; i <= n; ++i) { cnt[i] = 0; } for (int i = 1; i <= n; ++i) { ++cnt[ans[i]]; } for (int i = 1; i <= n; ++i) { if (cnt[i] != 1) { return 0; } } return 1; } void solve(int n) { for (int i = 1; i + 1 <= n; ++i) { mem[0][i] = query(i, i + 1); } for (int i = 1; i + 2 <= n; ++i) { mem[1][i] = query(i, i + 2); } for (int i = 1; i + 2 <= n; ++i) { t[i + 1] = (mem[0][i] + mem[0][i + 1]) == mem[1][i]; } for (int i = 1; i <= n; ++i) { r[i] = r[i - 1] ^ t[i]; } for (int f = 1; f <= n; ++f) { ans[1] = f; for (int i = 2; i <= n; ++i) { if (r[i]) { ans[i] = ans[i - 1] + mem[0][i - 1]; } else { ans[i] = ans[i - 1] - mem[0][i - 1]; } } if (check(n)) { for (int i = 1; i <= n; ++i) { answer(i, ans[i]); } return; } ans[1] = f; for (int i = 2; i <= n; ++i) { if (r[i]) { ans[i] = ans[i - 1] - mem[0][i - 1]; } else { ans[i] = ans[i - 1] + mem[0][i - 1]; } } if (check(n)) { for (int i = 1; i <= n; ++i) { answer(i, ans[i]); } return; } } }