Submission #1212789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212789		mychecksedad	Monster Game (JOI21_monster)	C++20	92 / 100	28 ms	424 KiB

monster

#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

namespace {
  void rev(vector<int> &V, int l, int r){
    for(int i = l; i <= (l+r)/2; ++i){
      swap(V[i], V[r - (i-l)]);
    }
  }

}  // namespace

vector<int> Solve(int n) {
  // vi v(n), res(n);
  // vector<vi> RES(n);
  // for(int i = 0; i < n; ++i){
  //   for(int j = i + 1; j < n; ++j){
  //     bool x = Query(i, j);
  //     x ? v[i]++ : v[j]++;
  //   }
  // }
  // for(int i = 0; i < n; ++i){
  //   if(v[i] != 1 && v[i] != n-2){
  //     res[i] = v[i];
  //     RES[v[i]].pb(i);
  //   }else{
  //     RES[v[i]].pb(i);
  //   }
  // }



  // bool x = !Query(RES[1][0], RES[2][0]) && (RES[2].size() == 1 ? true : !Query(RES[1][0], RES[2][1])); // whether it's beaten by both
  // if(x){
  //   res[RES[1][0]] = 0;
  //   res[RES[1][1]] = 1;
  // }else{
  //   res[RES[1][0]] = 1;
  //   res[RES[1][1]] = 0;
  // }

  // bool y = Query(RES[n-2][0], RES[n-3][0]) && (RES[n-3].size() == 1 ? true : Query(RES[n-2][0], RES[n-3][1])); // whether it's beats both
  // if(y){
  //   res[RES[n-2][0]] = n-1;
  //   res[RES[n-2][1]] = n-2;
  // }else{
  //   res[RES[n-2][0]] = n-2;
  //   res[RES[n-2][1]] = n-1;
  // }

  vi res(n, -1);

  vector<int> V;
  V.pb(0);
  for(int i = 1; i < n; ++i){
    int l = 0, r = int(V.size())-1, pos = V.size();  
    while(l <= r){
      int mid = l+r>>1;
      if(!Query(i, V[mid])){
        pos = mid;
        r = mid - 1;
      }else l = mid + 1;
    }
    V.insert(V.begin() + pos, i);
  }
  // now we got chains...
  // what do we do.. we got around N~ queries.


  // identify the first chain
  int last2 = 0, beat = 0;
  for(int i = 1; i < n; ++i){
    if(Query(V[0], V[i])){
      ++beat;
      last2 = i;
    }
  }
  if(beat == 1){
    cerr << "Case 1\n";
    // hardest case ngl
    if(last2 == 1){

      cerr << "Case 1.1\n";

      res[V[0]] = 0;
      res[V[1]] = 1;

      int largest = V[1], last = 1, j = 2;
      int cur = 2;
      for(; j < n; ++j){
        if(Query(largest, V[j])){
          // this is cur
          res[V[j]] = cur++;
          for(int l = j - 1; l > last; --l){
            res[V[l]] = cur++;
          }
          largest = V[last + 1];
          last = j;
        }
      }
    }else if(last2 > 2){

      cerr << "Case 1.2\n";
      bool bb = Query(V[1], V[last2]);
      if(bb){
        // 0 k k-1 ... 1
        res[V[0]] = 0;
        res[V[last2]] = 1;
        
        int cur = 2;

        for(int j = last2 - 1; j > 0; --j){
          res[V[j]] = cur++;
        }

        int largest = V[1], last = last2, j = last2 + 1;
        for(; j < n; ++j){
          if(Query(largest, V[j])){
            // this is cur
            res[V[j]] = cur++;
            for(int l = j - 1; l > last; --l){
              res[V[l]] = cur++;
            }
            largest = V[last + 1];
            last = j;
          }
        }
      }else{

        cerr << "Case 1.3\n";
        res[V[0]] = 1;
        res[V[1]] = 0;
        res[V[last2]] = 2;
      
        int cur = 3;

        for(int j = last2 - 1; j > 1; --j){
          res[V[j]] = cur++;
        }

        int largest = V[2], last = last2, j = last2 + 1;
        for(; j < n; ++j){
          if(Query(largest, V[j])){
            // this is cur
            res[V[j]] = cur++;
            for(int l = j - 1; l > last; --l){
              res[V[l]] = cur++;
            }
            largest = V[last + 1];
            last = j;
          }
        }
      }
    }else{
      cerr << "jump from the window\n";
      // idk jump from the window
      // 0 2 1 or 1 0 2, all 3 queries return the same... 
      int beat2 = 0;
      for(int i = 0; i < n; ++i) if(i != 1 && Query(V[1], V[i])) ++beat2;
      int cur = 3, last = 2, largest, j = 3;
      if(beat2 == 1){
        // 1 0 2
        res[V[0]] = 1;
        res[V[1]] = 0;
        res[V[2]] = 2;
        largest = V[2];
      }else{
        res[V[0]] = 0;
        res[V[1]] = 2;
        res[V[2]] = 1;
        largest = V[1];
      }
      for(; j < n; ++j){
        if(Query(largest, V[j])){
          // this is cur
          res[V[j]] = cur++;
          for(int l = j - 1; l > last; --l){
            res[V[l]] = cur++;
          }
          largest = V[last + 1];
          last = j;
        }
      }
    }
  }else if(beat == n-2){
    cerr << "Case 2\n";
    bool bb = Query(V.back(), V[1]);
    if(bb){
      // n-2 ... 0 n-1 case
      int cur = 0;
      for(int i = n-2; i >= 0; --i) res[V[i]] = cur++;
      res[V.back()] = n-1;
    }else{
      // n-1 n-2... 0 case
      int cur = 0;
      for(int i = n-1; i >= 0; --i) res[V[i]] = cur++;
    }
  }else{
    cerr << "Case 3\n";

    res[V[0]] = beat;
    int cur = beat - 1;
    int j = 1;
    for(; cur >= 0; ++j){
      res[V[j]] = cur--;
    }
    int largest = V[0], last = j - 1;
    cur = res[V[0]] + 1;
    for(; j < n; ++j){
      if(Query(largest, V[j])){
        // this is cur
        res[V[j]] = cur++;
        for(int l = j - 1; l > last; --l){
          res[V[l]] = cur++;
        }
        largest = V[last + 1];
        last = j;
      }
    }
  }

  return res;
}

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