Submission #1222324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222324		AlperenT_	Monster Game (JOI21_monster)	C++20	93 / 100	56 ms	48484 KiB

monster

#include "monster.h"

#include <bits/stdc++.h> 


#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =  1e6 + 100 , inf = 1e9 + 10 , mod = 1e9 + 7 ; 
int n , X[maxn] , p[maxn];
map <int,int> mp[maxn] ; 
int query(int a, int b){
  if(mp[a][b] == 0){
    mp[a][b] = Query(a,b)+1;
    mp[b][a] = 3 - mp[a][b] ;
    return mp[a][b]-1 ;
  }
  return mp[a][b]-1 ;
}
vector <int> mrg(int l,  int r){
  vector <int> v , vl , vr ; 
  if(l ==r){
    v.pb(l);
    return v; 
  }
  int mid = (l+r)/2 ;
  vl = mrg(l , mid) ;
  vr = mrg(mid+1,r);
  int i0 = 0, i1 = 0 ;
  while(i0 < sz(vl) && i1 < sz(vr)){
    if(query(vl[i0] , vr[i1])){
      v.pb(vr[i1]);i1++;
    }else{
      v.pb(vl[i0]);i0++;
    }
  }
  while(i0 < sz(vl)){
    v.pb(vl[i0]);i0++;
  }
  while(i1 < sz(vr)){
    v.pb(vr[i1]) ; i1++;
  }
  return v; 
}


std::vector<int> Solve(int N) {
  n = N ;
  vector <int>v ;
  v = mrg(0 ,n-1);
  int  ted =0 ;
  rep(i ,0 , n-1){
    if(i == v[0])continue ;
    if(query(v[0] , i)==1)ted++;
  }
  int fi ; 
  if(ted == 1){
    fi =1 ;
    int t =0 ;
    rep(i , 0 ,n-1){
      if(i==v[1])continue ;
      if(query(v[1] , i) == 1)t++ ;
    }
    if(t==1){
      fi =2 ;
    }
  }else if(ted == n-2){
    if(query(v[1] , v.back()) )fi = n ;
    else fi = n-1 ;
  }else{
    fi = ted+1 ;
  }
  int id =0 ;
  rep(i , 0 ,fi-1){
    p[i] = fi-i ;
  }
  int ls= fi-1 , x = fi , ls2 =0  ;
  rep(i , fi , n-1){
    if(query(v[ls2] , v[i]) == 1){
      per(j ,i ,ls+1){
        x++;
        p[j] = x ;
        ls2 = j ;
      }
      ls = i ; 
    }
  }
  vector <int> ans ;
  rep(i , 0 ,n-1){
    X[v[i]] = p[i] ;
  }
  rep(i , 0,n-1)ans.pb(X[i]-1);
  return ans ;
}

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