Submission #807455

#	Time	Username	Problem	Language	Result	Execution time	Memory
807455		farhan132	Monster Game (JOI21_monster)	C++17	100 / 100	100 ms	324 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

bool cmp(ll x, ll y){
    if(abs(x - y) == 1) return x > y;
    return x < y;
}

void print(vector < ll > x){
    for(auto u : x) cout << u << ' ';
    cout << '\n';
}

vector < ll > merge(vector < ll > a, vector < ll > b){
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    vector < ll > c;
    while(a.size() && b.size()){
        if(Query(a.back(), b.back()) == 0){
            c.pb(a.back());
            a.pop_back();
        }else{
            c.pb(b.back());
            b.pop_back();
        }
    }
    while(a.size()){
        c.pb(a.back());
        a.pop_back();
    }
    while(b.size()){
        c.pb(b.back());
        b.pop_back();
    }
    return c;
}

vector < ll > merge_sort(vector < ll > p){
    if(p.size() == 1) return p;
    vector < ll > x;
    vector < ll > y;
    for(ll i = 0; i < p.size()/2; i++){
        x.pb(p[i]);
    }
    for(ll i = p.size()/2; i < p.size(); i++){
        y.pb(p[i]);
    }
    x = merge_sort(x);
    y = merge_sort(y);
    p = merge(x, y);
    return p;
}

void rev(vector < ll > &v, ll l, ll r){
  ll m = (l + r) / 2;
  for(ll i = l; i <= m; i++) swap(v[i], v[r - (i - l)]);
  return;
}

vector < ll > gen(vector < ll > p){
  vector < ll > ans(p.size());
  for(ll i = 0; i < p.size(); i++){
    ans[p[i]] = i;
  }
  return ans;
}

std::vector<int> Solve(int n) {

  vector < ll > p(n);

  for(ll i = 0; i < n; i++) p[i] = i;

  p = merge_sort(p);

  vector < ll > cnt(n, 0);

  ll lmt = min(n, 10);

  for(ll i = 0; i < lmt; i++){
    for(ll j = 0; j < lmt; j++){
      if(i - j){
        if(Query(p[i], p[j])) cnt[i]++;
      }
    }
  }
  vector < ll > cands;
  for(ll i = 0; i < lmt; i++){
    if(cnt[i] == 1) cands.pb(i);
  }
  ll k = cands[0];
  if(cands.size() > 1){
    k = Query(p[cands[0]], p[cands[1]]);
    if(k == 1) k = cands[0];
    else k = cands[1];
  }

  rev(p, 0, k);

  while(k + 1 < n){
    ll c = k + 1;
    while(Query(p[k], p[c]) == 0) c++;
    rev(p, k + 1, c);
    k = c;
  }

  return gen(p);
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> merge_sort(std::vector<int>)':
monster.cpp:54:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(ll i = 0; i < p.size()/2; i++){
      |                   ~~^~~~~~~~~~~~
monster.cpp:57:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll i = p.size()/2; i < p.size(); i++){
      |                            ~~^~~~~~~~~~
monster.cpp: In function 'std::vector<int> gen(std::vector<int>)':
monster.cpp:74:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(ll i = 0; i < p.size(); i++){
      |                 ~~^~~~~~~~~~

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