Submission #741195

#	Time	Username	Problem	Language	Result	Execution time	Memory
741195		Charizard2021	The Big Prize (IOI17_prize)	C++17	Compilation error	0 ms	0 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
map<int, pair<int, int> > mp;
pair<int, int> Ask(int x){
	if(mp.find(x) != mp.end()){
        return mp[x];
    }
	auto q = ask(x);
	return mp[x] = make_pair<int, int>(q[0], q[1]);
}
int find_best(int n) {
	if(n <= 5000){
		for(int i = 0; i < n; i++) {
			vector<int> ans = ask(i);
			if(ans[0] + ans[1] == 0){
				return i;
            }
		}
	}
	vector<int> cur;
	for(int i = 0; i <= 500; i++){
		cur.push_back(((n-1) * i) / 500);
	}
	int value1 = 0;
	for(int i = 0; i < cur.size(); i++){
		pair<int, int> value2 = Ask(cur[i]);
		value1 = max(value1, value2.first + value2.second);
	}
	auto check = [&](int x){
		pair<int, int> value2 = Ask(x);
		return value2.first + value2.second != value1;
	};
	for(int i =0 ; i < n; i++){
		if(check(i)){
			pair<int, int> value2 = Ask(i);
			if(value2.first + value2.second == 0){
                return i;
            }
		}
		else{
			auto works = [&](int x, int y){
				if(check(y)) return true;
				auto value2 = Ask(x).second;
				auto q = Ask(y).second;
				return value2 != q;
			};
			int low = i + 1;
			int high = n + 100;
			for(auto &j : cur){
				if(j > i && works(i, j)){
					high = j;
					break;
				}
				low = max(low, j);
			}
			while(low != high){
				int mid = (low + high) / 2;
				if(works(i, mid)) high = mid;
				else low = mid + 1;
			}
			i = low - 1;
		}
	}
}

Compilation message (stderr)

prize.cpp:3:1: error: 'map' does not name a type
    3 | map<int, pair<int, int> > mp;
      | ^~~
prize.cpp:4:1: error: 'pair' does not name a type
    4 | pair<int, int> Ask(int x){
      | ^~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:14:4: error: 'vector' was not declared in this scope
   14 |    vector<int> ans = ask(i);
      |    ^~~~~~
prize.cpp:14:4: note: suggested alternatives:
In file included from /usr/include/c++/10/vector:67,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
prize.cpp:14:11: error: expected primary-expression before 'int'
   14 |    vector<int> ans = ask(i);
      |           ^~~
prize.cpp:15:7: error: 'ans' was not declared in this scope; did you mean 'abs'?
   15 |    if(ans[0] + ans[1] == 0){
      |       ^~~
      |       abs
prize.cpp:20:2: error: 'vector' was not declared in this scope
   20 |  vector<int> cur;
      |  ^~~~~~
prize.cpp:20:2: note: suggested alternatives:
In file included from /usr/include/c++/10/vector:67,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
prize.cpp:20:9: error: expected primary-expression before 'int'
   20 |  vector<int> cur;
      |         ^~~
prize.cpp:22:3: error: 'cur' was not declared in this scope
   22 |   cur.push_back(((n-1) * i) / 500);
      |   ^~~
prize.cpp:25:21: error: 'cur' was not declared in this scope
   25 |  for(int i = 0; i < cur.size(); i++){
      |                     ^~~
prize.cpp:26:3: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   26 |   pair<int, int> value2 = Ask(cur[i]);
      |   ^~~~
      |   std::pair
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
prize.cpp:26:8: error: expected primary-expression before 'int'
   26 |   pair<int, int> value2 = Ask(cur[i]);
      |        ^~~
prize.cpp:27:24: error: 'value2' was not declared in this scope; did you mean 'value1'?
   27 |   value1 = max(value1, value2.first + value2.second);
      |                        ^~~~~~
      |                        value1
prize.cpp:27:12: error: 'max' was not declared in this scope; did you mean 'std::max'?
   27 |   value1 = max(value1, value2.first + value2.second);
      |            ^~~
      |            std::max
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from prize.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: 'std::max' declared here
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
prize.cpp: In lambda function:
prize.cpp:30:3: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   30 |   pair<int, int> value2 = Ask(x);
      |   ^~~~
      |   std::pair
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
prize.cpp:30:8: error: expected primary-expression before 'int'
   30 |   pair<int, int> value2 = Ask(x);
      |        ^~~
prize.cpp:31:10: error: 'value2' was not declared in this scope; did you mean 'value1'?
   31 |   return value2.first + value2.second != value1;
      |          ^~~~~~
      |          value1
prize.cpp: In function 'int find_best(int)':
prize.cpp:35:4: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   35 |    pair<int, int> value2 = Ask(i);
      |    ^~~~
      |    std::pair
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
prize.cpp:35:9: error: expected primary-expression before 'int'
   35 |    pair<int, int> value2 = Ask(i);
      |         ^~~
prize.cpp:36:7: error: 'value2' was not declared in this scope; did you mean 'value1'?
   36 |    if(value2.first + value2.second == 0){
      |       ^~~~~~
      |       value1
prize.cpp: In lambda function:
prize.cpp:43:19: error: 'Ask' was not declared in this scope; did you mean 'ask'?
   43 |     auto value2 = Ask(x).second;
      |                   ^~~
      |                   ask
prize.cpp: In function 'int find_best(int)':
prize.cpp:49:18: error: 'cur' was not declared in this scope
   49 |    for(auto &j : cur){
      |                  ^~~
prize.cpp:54:11: error: 'max' was not declared in this scope; did you mean 'std::max'?
   54 |     low = max(low, j);
      |           ^~~
      |           std::max
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from prize.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: 'std::max' declared here
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~