| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084166 | yoav_s | Monster Game (JOI21_monster) | 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;
typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
const ll INF = 1e18;
const ll mod = 1e9 + 7;
#include "monster.h"
bool wins(ll a, ll b)
{
if (abs(a - b) == 1)
{
return a < b;
}
return a > b;
}
void solveRec(v curValues, v curOptions, vector<int> &res)
{
if (curValues.size() == 1)
{
res[curValues[0]] = curOptions[0];
return;
}
if (curValues.size() == 0) return;
ll n = curValues.size();
vb isValue(1000, false);
for (ll x : curOptions) isValue[x] = true;
v winningCnt(n);
for (ll i = 0; i < n; i++)
{
ll x = curOptions[i];
winningCnt[i] = i;
if (x < 999 && isValue[x + 1]) winningCnt[i]++;
if (x > 0 && isValue[x - 1]) winningCnt[i]--;
}
vv byWinCnt(n);
for (ll i = 0; i < n; i++) byWinCnt[winningCnt[i]].pb(i);
bool poss = false;
for (ll i= 0; i < n; i++) poss = poss || byWinCnt[i].size() == 1;
if (!poss)
{
vvb valWinning(n, vb(n, false));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < i; j++)
{
if (Query(curValues[i], curValues[j])) valWinning[i][j] = true;
else valWinning[i][j] = false;
valWinning[j][i] = !valWinning[i][j];
}
}
vvb optWinning(n, vb(n, false));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < i; j++)
{
if (wins(curValues[i], curValues[j])) optWinning[i][j] = true;
else optWinning[i][j] = false;
optWinning[j][i] = !optWinning[i][j];
}
}
v assignment(n);
for (ll i = 0; i < n; i++) assignment[i] = i;
do
{
bool valid = true;
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < n; j++)
{
if (valWinning[i][j] != optWinning[assignment[i]][assignment[j]])
{
valid = false; break;
}
}
}
if (valid) break;
} while (next_permutation(all(assignment)));
for (ll i = 0; i < n; i++)
{
res[curValues[i]] = curOptions[assignment[i]];
}
return;
}
while (true)
{
ll cur = rand() % n;
ll iWinCnt = 0;
vb iWin(n, false);
for (ll i = 0; i < n; i++)
{
if (i == cur) continue;
iWin[i] = Query(curValues[cur], curValues[i]);
iWinCnt += iWin[i];
}
if (byWinCnt[iWinCnt].size() == 1)
{
res[curValues[cur]] = curOptions[byWinCnt[iWinCnt][0]];
ll actVal = curValues[cur];
ll actOption = curOptions[byWinCnt[iWinCnt][0]];
v smallerVal, biggerVal;
for (ll i = 0; i < n; i++)
{
if (i == cur) continue;
if (iWin[i]) smallerVal.pb(curValues[i]);
else biggerVal.pb(curValues[i]);
}
v smallerOptions, biggerOptions;
for (ll i = 0; i < n; i++)
{
if (curOptions[i] == actOption) continue;
if (wins(actOption, curOptions[i])) smallerOptions.pb(curOptions[i]);
else biggerOptions.pb(curOptions[i]);
}
solveRec(smallerVal, smallerOptions, res);
solveRec(biggerVal, biggerOptions, res);
break;
}
}
}
vector<int> Solve(int N)
{
v vals(N), options(N);
vector<int> res(N);
for (ll i = 0; i< N; i++) vals[i] = options[i] = i;
solveRec(vals, options, res);
return res;
}
namespace {
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
constexpr int Q_MAX = 25'000;
constexpr int N_MAX = 1'000;
int N;
int S[N_MAX];
int query_count = 0;
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
} // namespace
bool Query(int a, int b) {
if (++query_count > Q_MAX) WrongAnswer(6);
if (a < 0 || N <= a || b < 0 || N <= b) WrongAnswer(4);
if (a == b) WrongAnswer(5);
return (S[a] > S[b]) ^ (abs(S[a] - S[b]) == 1);
}
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading.\n");
exit(1);
}
for (int i = 0; i < N; i++) {
if (scanf("%d", S + i) != 1) {
fprintf(stderr, "Error while reading.\n");
exit(1);
}
}
std::vector<int> T = Solve(N);
if ((int)T.size() != N) WrongAnswer(1);
for (int i = 0; i < N; i++) {
if (T[i] < 0 || N <= T[i]) WrongAnswer(2);
if (T[i] != S[i]) WrongAnswer(3);
}
printf("Accepted: %d\n", query_count);
return 0;
}
/**/