Submission #1084164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084164		yoav_s	Monster Game (JOI21_monster)	C++17	0 / 100	76 ms	924 KiB

monster

#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 < n; 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;
}
/**/

Compilation message (stderr)

monster.cpp:205:1: warning: "/*" within comment [-Wcomment]
  205 | /**/
      |  
monster.cpp: In function 'void solveRec(v, v, std::vector<int>&)':
monster.cpp:124:16: warning: unused variable 'actVal' [-Wunused-variable]
  124 |             ll actVal = curValues[cur];
      |                ^~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75