Submission #616061

#	Time	Username	Problem	Language	Result	Execution time	Memory
616061		AbdelmagedNour	Monster Game (JOI21_monster)	C++17	100 / 100	144 ms	300 KiB

monster

#include<bits/stdc++.h>
#include "monster.h"
//#include"grader.cpp"
using namespace std;
mt19937 mt(time(NULL));
vector<int>brute_force(vector<int>v){
    int n=v.size();
    vector<vector<bool>>res(n,vector<bool>(n,0));
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            res[j][i]=!(res[i][j]=Query(v[i],v[j]));
    vector<pair<int,int>>cnt(n);
    for (int i=0;i<n;i++)
        cnt[i]={count(res[i].begin(),res[i].end(),1),v[i]};
    sort(cnt.begin(),cnt.end());
    for(int i=0;i<n;i++)v[i]=cnt[i].second;
    if(Query(v[1],v[0]))swap(v[0],v[1]);
    if(Query(v[n-1],v[n-2]))swap(v[n-2],v[n-1]);
    return v;
}
vector<int>merge_sort(vector<int>v){
  if(v.size()==1)return v;
  shuffle(v.begin(),v.end(),mt);
  int m=v.size()/2;
  vector<int>l(v.begin(),v.begin()+m),r(v.begin()+m,v.end());
  l=merge_sort(l);
  r=merge_sort(r);
  int i=0,j=0;
  for(int k=0;k<v.size();k++) {
        if(i==l.size())v[k]=r[j++];
        else if(j==r.size())v[k]=l[i++];
        else if(Query(l[i],r[j]))v[k]=r[j++];
        else v[k]=l[i++];
    }
    return v;
}
vector<int>Solve(int N){
    vector<int>res(N);
    iota(res.begin(),res.end(),0);
    res=merge_sort(res);
    vector<int>s(res.begin(),res.begin()+min(13,N));
    s=brute_force(s);
    int zero=s[0];
    res.erase(find(res.begin(),res.end(),zero));
    res.insert(res.begin(),zero);
    for(int i=1;i<N;i++){
        int j=i;
        while(j<N&&Query(res[j],zero))j++;
        reverse(res.begin()+i,res.begin()+min(j + 1, N));
        zero=res[j];
        i=j;
    }
    vector<int>ans(N);
    for(int i=0;i<N;i++)ans[res[i]]=i;
    return ans;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> merge_sort(std::vector<int>)':
monster.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int k=0;k<v.size();k++) {
      |               ~^~~~~~~~~
monster.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if(i==l.size())v[k]=r[j++];
      |            ~^~~~~~~~~~
monster.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         else if(j==r.size())v[k]=l[i++];
      |                 ~^~~~~~~~~~

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