Submission #894102

#	Time	Username	Problem	Language	Result	Execution time	Memory
894102		MilosMilutinovic	Monster Game (JOI21_monster)	C++17	0 / 100	54 ms	1828 KiB

monster

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

using namespace std;

namespace {

bool example_variable;

}  // namespace

vector<int> Solve(int n) {
  map<pair<int, int>, bool> mp;
  function<bool(int, int)> Ask = [&](int x, int y) {
    if (x > y) {
      return !Ask(y, x);
    }
    if (!mp.count({x, y})) {
      mp[{x, y}] = Query(x, y);
    }
    return mp[{x, y}];
  };
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  vector<int> tmp(n);
  function<void(int, int)> MergeSort = [&](int l, int r) {
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    MergeSort(l, mid);
    MergeSort(mid + 1, r);
    for (int i = l; i <= r; i++) {
      tmp[i] = order[i];
    }
    int pl = l, pr = mid + 1;
    int ptr = l;
    while (pl <= mid || pr <= r) {
      if (pl > mid) {
        order[ptr++] = tmp[pr++];
      } else if (pr > r) {
        order[ptr++] = tmp[pl++];
      } else {
        order[ptr++] = (Ask(tmp[pl], tmp[pr]) ? tmp[pl++] : tmp[pr++]);
      }
    }
  };
  MergeSort(0, n - 1);
  int pos = -1;
  auto Check = [&]() {
    if (Ask(order[0], order[2])) {
      return false;
    }
    if (!Ask(order[0], order[1])) {
      return false;
    }
    if (!Ask(order[1], order[2])) {
      return false;
    }
    return true;
  };
  int to = -1;
  if (n <= 10) {
    vector<int> bad;
    for (int i = 1; i < n; i++) {
      if (!Ask(order[0], order[i])) {
        bad.push_back(i);
      }
    }
    if ((int) bad.size() > 1) {
      pos = bad.rbegin()[1];
    } else {
      bool ok = true;
      for (int i = 2; i < n; i++) {
        if (!Ask(order[1], order[i])) {
          ok = false;
          break;
        }
      }
      if (ok) {
        pos = 1;
      } else {
        pos = 0;
      }
    }
  } else {
    if (Check()) {
      if (!Ask(order[0], order[3]) && !Ask(order[1], order[3])) {
        vector<int> bad;
        for (int i = 1; i < n; i++) {
          if (!Ask(order[0], order[i])) {
            bad.push_back(i);
          }
        }
        pos = bad.rbegin()[1];
      } else {
        vector<int> cnt(3);
        auto Update = [&](int x) {
          for (int i = 0; i < 3; i++) {
            if (cnt[i] > 0) {
              return;
            }
          }
          for (int i = 0; i < 3; i++) {
            cnt[i] += !Ask(order[i], x);
          }
        };
        if (!Ask(order[3], order[5]) && Ask(order[3], order[4]) && Ask(order[4], order[5])) {
          if (!Ask(order[3], order[6]) && !Ask(order[4], order[6])) {
            vector<int> bad(order[6]);
            int cnt = 0;
            for (int i = 7; i < n; i++) {
              if (!Ask(order[3], order[i])) {
                bad.push_back(order[i]);
                cnt = 0;
              } else {
                cnt += 1;
                if (cnt >= 1) {
                  break;
                }
              }
            }
            if (cnt >= 1) {
              to = bad.back();
              Update(bad.back());
            } else {
              if ((int) bad.size() > 1) {
                bad.pop_back();
              }
              to = bad.back();
              Update(bad.back());
            }
          } else {
            for (int i = 3; i < 6; i++) {
              Update(order[i]);
            }
          }
        } else {
          Update(order[4]);
          Update(order[3]);
        }
        for (int i = 0; i < 3; i++) {
          if (cnt[i] > 0) {
            pos = (i - 1 + 3) % 3;
            break;
          }
        }
      }
    } else {
      vector<int> cnt(2);
      auto Update = [&](int x) {
        for (int i = 0; i < 2; i++) {
          if (cnt[i] > 0) {
            return;
          }
        }
        for (int i = 0; i < 1; i++) {
          cnt[i] += !Ask(order[i], x);
        }
      };
      if (!Ask(order[2], order[4]) && Ask(order[2], order[3]) && Ask(order[3], order[4])) {
        if (!Ask(order[2], order[5]) && !Ask(order[3], order[5])) {
          vector<int> bad(order[5]);
          int cnt = 0;
          for (int i = 6; i < n; i++) {
            if (!Ask(order[2], order[i])) {
              bad.push_back(order[i]);
              cnt = 0;
            } else {
              cnt += 1;
              if (cnt >= 1) {
                break;
              }
            }
          }
          if (cnt >= 1) {
            to = bad.back();
            Update(bad.back());
          } else {
            if ((int) bad.size() > 1) {
              bad.pop_back();
            }
            to = bad.back();
            Update(bad.back());
          }
        } else {
          for (int i = 2; i < 5; i++) {
            Update(order[i]);
          }
        }
      } else {
        Update(order[3]);
        Update(order[2]);
      }
      for (int i = 0; i < 2; i++) {
        if (cnt[i] > 0) {
          pos = (i - 1 + 2) % 2;
          break;
        }
      }
    }
  }
  vector<int> res;
  function<void(int, int)> Solve = [&](int l, int r) {
    for (int i = r; i >= l; i--) {
      res.push_back(order[i]);
    }
    if (r == n - 1) {
      return;
    }
    if (r == pos && to != -1) {
      Solve(r + 1, to);
      return;
    }
    for (int i = r + 1; i < n; i++) {
      if (i == n - 1 || Ask(order[l], order[i]) == (l != l)) {
        Solve(r + 1, i);
        break;
      }
    }
  };
  Solve(0, pos);
  reverse(res.begin(), res.end());
  vector<int> ret(n);
  for (int i = 0; i < n; i++) {
    ret[res[i]] = i;
  }
  return ret;
}

Compilation message (stderr)

monster.cpp: In lambda function:
monster.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~
monster.cpp: In lambda function:
monster.cpp:216:55: warning: self-comparison always evaluates to false [-Wtautological-compare]
  216 |       if (i == n - 1 || Ask(order[l], order[i]) == (l != l)) {
      |                                                     ~ ^~ ~
monster.cpp: At global scope:
monster.cpp:8:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
    8 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

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