Submission #1084209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084209		yoav_s	Monster Game (JOI21_monster)	C++17	10 / 100	160 ms	600 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;
}

vector<int> Solve(int N)
{
    vvb winning(N, vb(N, false));
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j < i; j++)
        {
            winning[i][j] = Query(i, j);
            winning[j][i] = !winning[i][j];
        }
    }
    v winningAmt(N);
    for (ll i =0 ; i < N; i++)
    {
        for (ll j = 0; j < N; j++) winningAmt[i] += winning[i][j];
    }
    vv byAmt(N);
    for (ll i = 0; i < N; i++) byAmt[winningAmt[i]].pb(i);
    vector<int> res(N);
    for (ll i = 2; i < N - 2; i++)
    {
        res[byAmt[i][0]] = i;
    }
    if (winning[byAmt[1][0]][byAmt[1][1]])
    {
        res[byAmt[1][0]] = 0;
        res[byAmt[1][1]] = 1;
    }
    else
    {
        res[byAmt[1][0]] = 1;
        res[byAmt[1][1]] = 0;
    }
    if (winning[byAmt[N - 2][0]][byAmt[N - 2][1]])
    {
        res[byAmt[N - 2][0]] = N - 2;
        res[byAmt[N - 2][1]] = N - 1;
    }
    else
    {
        res[byAmt[N - 2][0]] = N - 1;
        res[byAmt[N - 2][1]] = N - 2;
    }
    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:136:1: warning: "/*" within comment [-Wcomment]
  136 | /**/
      |

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