Submission #1198952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198952		dosts	The Big Prize (IOI17_prize)	C++20	Compilation error	0 ms	0 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

const int inf = 2e9;
map<int,vi> cache;
int asked = 0;
vi myask(int p) {
	if (cache.count(p)) return cache[p];
	asked++;
	return cache[p] = ask(p);
}

int find_best(int n) {
	set<int> possible;
	int mx = 0;
	srand(time(0));
	int select;
	for (int i = 0;i<450 && i<n;i++) {
		vi v = myask(i);
		if (v[0]+v[1] == 0) return 0;
		if (v[0]+v[1] > mx) {
			mx = v[0]+v[1];
			select = i;
		}
	}
	for (int i=0;i<n;i++) possible.insert(i);
	int pl = select,pr = select;
	while (possible.size() >= 5000-asked) {
		if (pl <= 0) break;
		vector<int> q = myask(pl);
		vi prv = myask(pl-1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pl-1;
			while (ptr > 0) {
				prv = myask(ptr-1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr--;
				else break;
			}
			pl = ptr-1;
			continue;
		}
		int l = 0;
		int r = pl-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = myask(m);
			if (vv[0]+vv[1] == 0) return m;
			if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[1] > q[1])) l = m+1;
			else r = m-1;
		}
		for (int j = pl;j >= l;j--) possible.erase(j);
		pl = l;
	}
	while (possible.size() >= 5000-asked) {
		if (pr >= n-1) break;
		vector<int> q = myask(pr);
		vi prv = myask(pr+1);
		if ((prv[0]+prv[1]) != (q[0]+q[1])) {
			int ptr = pr+1;
			while (ptr < n-1) {
				prv = myask(ptr+1);
				if (prv[0]+prv[1] == 0) return ptr-1;
				if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++;
				else break;
			}
			pr = ptr+1;
			continue;
		}
		int l = pr+1;
		int r = n-1;
		while (l<=r) {
			int m = (l+r) >> 1;
			vi vv = myask(m);
			if (vv[0]+vv[1] == 0) return m;
			if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1;
			else l = m+1;
		}
		for (int j = pr;j <= r;j++) possible.erase(j);
		pr = r;
	}
	vi v;
	for (auto it : possible) v.push_back(it);
	random_shuffle(all(v),mt19937_64(0));
	for (auto it : v) {
		vi vv = myask(it);
		if (vv[0] + vv[1] == 0) return it;
	}
	assert(0);
}

Compilation message (stderr)

In file included from /usr/include/c++/11/vector:62,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/11/bits/stl_algo.h: In instantiation of 'void std::random_shuffle(_RAIter, _RAIter, _Generator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Generator = std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>]':
prize.cpp:92:16:   required from here
/usr/include/c++/11/bits/stl_algo.h:4619:55: error: no match for call to '(std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>) (__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type)'
 4619 |           _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
      |                                                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/random:51,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:108,
                 from prize.cpp:2:
/usr/include/c++/11/bits/random.tcc:450:5: note: candidate: 'std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::operator()() [with _UIntType = long unsigned int; long unsigned int __w = 64; long unsigned int __n = 312; long unsigned int __m = 156; long unsigned int __r = 31; _UIntType __a = 13043109905998158313; long unsigned int __u = 29; _UIntType __d = 6148914691236517205; long unsigned int __s = 17; _UIntType __b = 8202884508482404352; long unsigned int __t = 37; _UIntType __c = 18444473444759240704; long unsigned int __l = 43; _UIntType __f = 6364136223846793005; std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type = long unsigned int]'
  450 |     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d,
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  451 |                             __s, __b, __t, __c, __l, __f>::
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/random.tcc:450:5: note:   candidate expects 0 arguments, 1 provided