답안 #705046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705046	2023-03-03T09:53:19 Z	MtSaka	Monster Game (JOI21_monster)	C++17	컴파일 오류	0 ms	0 KB

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;
  }
  rep(i,0,n)if(cnt[i]==1){
    rep(j,i+1,n)if(cnt[j]==1){
      if(a[i][j])return i
      else return j;
      break;
    }
    return i;
    break;
  }
  return -1;
}
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 mi=sol2(tmp);
  int start=id[mi];
  id.erase(id.begin()+mi);
  id.insert(id.begin(),start);
  rep(i,1,n){
    ll 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=v[j];
    i=j;
  }
  vector<int>ret(n);
  rep(i,0,n)ret[id[i]]=i;
  return ret;
}

Compilation message

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++];
      |             ~^~~~~~~~~~
monster.cpp: In function 'int sol2(const std::vector<int>&)':
monster.cpp:46:26: error: expected ';' before 'else'
   46 |       if(a[i][j])return i
      |                          ^
      |                          ;
   47 |       else return j;
      |       ~~~~                
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:67:46: error: no matching function for call to 'min(ll, int&)'
   67 |     reverse(id.begin()+i,id.begin()+min(j+1,n));
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from monster.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
monster.cpp:67:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   67 |     reverse(id.begin()+i,id.begin()+min(j+1,n));
      |                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from monster.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
monster.cpp:67:46: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   67 |     reverse(id.begin()+i,id.begin()+min(j+1,n));
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
monster.cpp:67:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   67 |     reverse(id.begin()+i,id.begin()+min(j+1,n));
      |                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from monster.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
monster.cpp:67:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   67 |     reverse(id.begin()+i,id.begin()+min(j+1,n));
      |                                              ^
monster.cpp:69:11: error: 'v' was not declared in this scope
   69 |     start=v[j];
      |           ^