제출 #1212823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212823		mychecksedad	Monster Game (JOI21_monster)	C++20	100 / 100	23 ms	428 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)]);
    }
  }

  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

  int rn(int l, int r){
    return uniform_int_distribution<int>(l,r)(rng);
  }

  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) {
  if(n * (n-1) <= 10000){
    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;
    }
    return res;
  }

  vi u;

  for(int i = 1; i <= n; ++i){
    u.pb(i-1);
    swap(u[i-1], u[rn(0, i-1)]);
  }


  vi res(n, -1);
  V.clear();
  V.pb(u[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(u[i], V[mid])){
        pos = mid;
        r = mid - 1;
      }else l = mid + 1;
    }
    V.insert(V.begin() + pos, u[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 < 15; ++i){
    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 = 1;
      for(int i = 2; i < 25; ++i) if(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: 75 / 75