Submission #1212802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212802		mychecksedad	Monster Game (JOI21_monster)	C++20	92 / 100	28 ms	420 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)]);
    }
  }
  vector<int> V;
  void solve_rest(int largest, int j, int cur, int last, vector<int> &res){
    for(; j < V.size(); ++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;
      }
    }
  }

}  // namespace

vector<int> Solve(int n) {
  vi res(n, -1);
  V.clear();
  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 = -1, beat = 0;
  int cnt = 0;
  for(int i = 1; i < n; ++i){
    if(cnt == 2) break;
    if(Query(V[0], V[i])){
      if(i == 1){
        last2 = 1;
        beat = 1;
        break;
      }
      if(last2 < i - 1) ++cnt; 
      ++beat;
      last2 = i;
    }
  }
  // cerr << last2 << " hell\n";
  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;
      
      solve_rest(largest, j, cur, last, res);
    }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;
        
        solve_rest(largest, j, cur, last, res);
      }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;
        
        solve_rest(largest, j, cur, last, res);
      }
    }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];
      }
      
      solve_rest(largest, j, cur, last, res);
    }
  }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--;
    }

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

    int largest = V[j], last = last2;
    
    solve_rest(largest, last2 + 1, cur, last, res);
  }

  return res;
}

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