Submission #1124324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124324		epicci23	Rarest Insects (IOI22_insects)	C++17	Compilation error	0 ms	0 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

const int N = 2e3 + 5;

map<vector<int>,int> Cache;
vector<int> ar;
int vis[N], Kill[N] , D , tot = 0;

inline bool Add(int x){
  if(vis[x] || Kill[x]) return 0;
  vis[x]=1;
  tot++;
  move_inside(x);
  return 1;
}

inline bool Rem(int x){
  if(!vis[x] || Kill[x]) return 0;
  vis[x]=0;
  tot--;
  move_outside(x);
  return 1;
}

random_device rd;

inline int Get(){
  vector<int> v;
  for(int i=0;i<N;i++) if(vis[i]) v.push_back(i);
  if(Cache.count(v)) return Cache[v];
  return Cache[v] = press_button();
}

int min_cardinality(int n){
  for(int i=0;i<n;i++) ar.push_back(i);
  shuffle(ar.begin(),ar.end(),mt19937(rd));
  for(int i : ar){
    Add(i);
    if(i == 0 || Get() == 1) continue;
    Rem(i);
  }
  for(int i : ar) if(vis[i]) Kill[i] = 1;
  D = tot;
  if(D > n / 2) return 1;
  if(D == 1) return n;

  int ans = 1, l = 2 , r = n / D;
  while(l <= r){
    int B = (l + r) / 2;
    for(int i : ar) if(!Kill[i]) Rem(i);
    vector<int> to_kill;
    for(int i : ar){
      if(vis[i] || Kill[i]) continue;
      Add(i);
      if(tot > B && Get() > B){
       Rem(i);
       to_kill.push_back(i);
      }
    }
    if(tot == B * D){
      l = B + 1;
      ans = B;
      r = min(r, B + (int) to_kill.size() / D);
      if(to_kill.size() < D) return ans;
      for(int i : ar) if(vis[i]) Kill[i] = 1;
    }
    else{
      for(int x : to_kill) Kill[x] = 1;
      r = min(tot / D, B - 1);
    }
  }

  return ans;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:38:41: error: no matching function for call to 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::mersenne_twister_engine(std::random_device&)'
   38 |   shuffle(ar.begin(),ar.end(),mt19937(rd));
      |                                         ^
In file included from /usr/include/c++/11/random:49,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:108,
                 from insects.cpp:2:
/usr/include/c++/11/bits/random.h:541:9: note: candidate: 'template<class _Sseq, class> std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mersenne_twister_engine(_Sseq&) [with _Sseq = _Sseq; <template-parameter-2-2> = <template-parameter-1-2>; _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253]'
  541 |         mersenne_twister_engine(_Sseq& __q)
      |         ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/random.h:541:9: note:   template argument deduction/substitution failed:
/usr/include/c++/11/bits/random.h: In substitution of 'template<class _UIntType, long unsigned int __w, long unsigned int __n, long unsigned int __m, long unsigned int __r, _UIntType __a, long unsigned int __u, _UIntType __d, long unsigned int __s, _UIntType __b, long unsigned int __t, _UIntType __c, long unsigned int __l, _UIntType __f> template<class _Sseq> using _If_seed_seq = typename std::enable_if<std::__detail::__is_seed_seq<_Sseq, std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>, _UIntType>::value>::type [with _Sseq = std::random_device; _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253]':
/usr/include/c++/11/bits/random.h:539:32:   required from here
/usr/include/c++/11/bits/random.h:502:15: error: 'class std::random_device' has no member named 'generate'
  502 |         using _If_seed_seq = typename enable_if<__detail::__is_seed_seq<
      |               ^~~~~~~~~~~~
/usr/include/c++/11/bits/random.h:530:7: note: candidate: 'std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mersenne_twister_engine(std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type) [with _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253; std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type = long unsigned int]'
  530 |       mersenne_twister_engine(result_type __sd)
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/random.h:530:43: note:   no known conversion for argument 1 from 'std::random_device' to 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'}
  530 |       mersenne_twister_engine(result_type __sd)
      |                               ~~~~~~~~~~~~^~~~
/usr/include/c++/11/bits/random.h:527:7: note: candidate: 'std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mersenne_twister_engine() [with _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253]'
  527 |       mersenne_twister_engine() : mersenne_twister_engine(default_seed) { }
      |       ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/random.h:527:7: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/11/bits/random.h:472:11: note: candidate: 'constexpr std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::mersenne_twister_engine(const std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&)'
  472 |     class mersenne_twister_engine
      |           ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/random.h:472:11: note:   no known conversion for argument 1 from 'std::random_device' to 'const std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&'
/usr/include/c++/11/bits/random.h:472:11: note: candidate: 'constexpr std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::mersenne_twister_engine(std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&&)'
/usr/include/c++/11/bits/random.h:472:11: note:   no known conversion for argument 1 from 'std::random_device' to 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>&&'