Submission #1307967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307967		M_W_13	Monster Game (JOI21_monster)	C++20	0 / 100	29 ms	412 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
vector<int> T;
int n;

void mergesort(int l, int r) {
  if (l == r) return ;
  int sr = (l + r)/2;
  mergesort(l, sr);
  mergesort(sr + 1, r);
  vector<int> A;
  vector<int> B;
  for (int i = l; i <= sr; i++) A.pb(T[i]);
  for (int i = sr + 1; i <= r; i++) B.pb(T[i]);
  int ita = 0;
  int itb = 0;
  int sza = A.size();
  int szb = B.size();
  int it = l;
  while (ita < sza || itb < szb) {
    if (ita == sza) {
      T[it] = B[itb];
      itb++;
    }
    else if (itb == szb) {
      T[it] = A[ita];
      ita++;
    }
    else {
      if (Query(A[ita], B[itb])) {
        T[it] = B[itb];
        itb++;
      }
      else {
        T[it] = A[ita];
        ita++;
      }
    }
    it++;
  }
}

std::vector<int> Solve(int N) {
  n = N;
  rep(i, n) T.pb(i);
  mergesort(0, n - 1);
  // rep(i, n) {
  //   cout << T[i] << " ";
  // }
  // cout << '\n';
  int it = 0;
  while (it < n) {
    if (it > 0) {
      if (Query(T[it - 1], T[it])) {
        it++;
        continue;
      }
    }
    else if (it == 0) {
      int cnt = 0;
      int kt = -1;
      for (int a = 1; a < n; a++) {
        if (Query(T[it], T[a])) {
          // cout << "a = " << a << endl;
          // cout << "T[a] = " << T[a] << endl;
          cnt++;
          kt = a;
        }
      }
      // cout << "cnt = " << cnt << endl;
      if (cnt == 1) {
        cnt = 0;
        // cout << "kt = " << kt << endl;
        for (int a = 0; a < n; a++) {
          if (a == kt) continue;
          if (Query(T[kt], T[a])) cnt++;
        }
        if (cnt == 1) {
          it++;
          continue;
        }
      }
    }
    int i = it + 2;
    int poc = it;
    while (i < n && (Query(T[it], T[i]))) {
      it++;
      i++;
    }
    it = poc;
    vector<int> pom;
    for (int x = it; x < i; x++) pom.pb(T[x]);
    reverse(all(pom));
    for (int x = it; x < i; x++) T[x] = pom[x - it];
    it = i;
  }
  vector<int> ans;
  ans.resize(n);
  rep(i, n) ans[T[i]] = i;
  return ans;
}

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