Submission #1222316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222316		AlperenT_	Monster Game (JOI21_monster)	C++20	25 / 100	90 ms	49652 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 ;
}
int Query2(int a ,int b){
  return query(b,a) ;
}

std::vector<int> Solve(int N) {
  n = N ;
  vector <int>v ;
  rep(i , 0 ,n-1)v.pb(i);  
  sort(all(v) , Query2) ;
  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: 0 / 75