Submission #705053

#	Time	Username	Problem	Language	Result	Execution time	Memory
705053		MtSaka	Monster Game (JOI21_monster)	C++17	100 / 100	116 ms	912 KiB

monster

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
#include "monster.h"
map<pair<int,int>,bool>mp;
bool ask(int a,int b){
  if(mp.count({a,b}))return mp[{a,b}];
  if(mp.count({b,a}))return !mp[{b,a}];
  return mp[{a,b}]=Query(a,b);
}
void merge(vector<int>&v){
  if(v.size()==1)return;
  int mid=v.size()/2;
  vector<int>l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
  merge(l),merge(r);
  int i=0,j=0;
  rep(k,0,v.size()){
    if(i==l.size())v[k]=r[j++];
    else if(j==r.size())v[k]=l[i++];
    else if(ask(l[i],r[j]))v[k]=r[j++];
    else v[k]=l[i++];
  }
  return;
}
int sol2(const vector<int>&id){
  int n=id.size();
  vector<int>cnt(n,0);
  vector<vector<int>>a(n,vector<int>(n,0));
  rep(i,0,n)rep(j,i+1,n){
    bool f=ask(id[i],id[j]);
    if(f)cnt[i]++;
    else cnt[j]++;
    a[i][j]=f;
    a[j][i]=!f;
  }
  vector<pair<int,int>>v(n);
  rep(i,0,n)v[i]={cnt[i],id[i]};
  sort(all(v));
  if(ask(v[1].second,v[0].second))swap(v[0],v[1]);
  return v[0].second;
}
vector<int>Solve(int n){
  vector<int>id(n);
  iota(id.begin(),id.end(),0);
  merge(id);
  vector<int>tmp(id.begin(),id.begin()+min(10,n));
  int start=sol2(tmp);
  id.erase(find(all(id),start));
  id.insert(id.begin(),start);
  rep(i,1,n){
    int j=i;
    while(j<n&&ask(id[j],start))j++;
    reverse(id.begin()+i,id.begin()+min(j+1,n));
    if(j==n)break;
    start=id[j];
    i=j;
  }
  vector<int>ret(n);
  rep(i,0,n)ret[id[i]]=i;
  return ret;
}

Compilation message (stderr)

monster.cpp: In function 'void merge(std::vector<int>&)':
monster.cpp:26:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(i==l.size())v[k]=r[j++];
      |        ~^~~~~~~~~~
monster.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     else if(j==r.size())v[k]=l[i++];
      |             ~^~~~~~~~~~

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