Submission #1028738

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1028738	2024-07-20T07:54:34 Z	parsadox2	The Big Prize (IOI17_prize)	C++17	Compilation error	0 ms	0 KB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n;
bool marked[N] , dead[N];

int Sq(int val)
{
	for(int i = 1 ; i <= val ; i++)  if(i * i >= val)
		return i;
	return -1;
}

void Solve()
{
	vector <int> all;
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		all.push_back(i);
	int m = all.size() , sq = Sq(m);
	if(m == 1)
		return;
	if(m < 500)
	{
		for(auto u : m)
		{
			auto now = ask(u);
			if(now[0] + now[1] != 0)
				dead[u] = true;
		}
		return;
	}
	int mx = 0;
	for(int i = 0 ; i < sq ; i++)
	{
		auto now = ask(all[i]);
		mx = max(mx , now[0] + now[1]);
	}
	for(auto u : all)
		marked[u] = false;
	for(int asd = 0 ; asd < mx ; asd++)
	{
		all.clear();
		for(int i = 0 ; i < n ; i++)  if(!dead[i] && !marked[i])
			all.push_back(i);
		m = all.size();
		int low = -1 , high = m;
		while(high - low > 1)
		{
			int mid = (low + high) >> 1;
			int id = all[mid];
			auto now = ask(id);
			if(now[0] + now[1] != mx)
			{
				marked[id] = true;
				break;
			}
			dead[id] = true;
			for(int i = 0 ; i < id ; i++)  if(!dead[i] && marked[i])
				now[0]--;
			if(now[0] == 0)
				low = mid;
			else
				high = mid;
		}
	}
	for(int i = 0 ; i < n ; i++)  if(!marked[i])
		dead[i] = true;
	Solve();
}

int find_best(int nn) {
	n = nn;
	Solve();
	for(int i = 0 ; i < n ; i++)  if(!dead[i])
		return i;
	return -1;
}

Compilation message

prize.cpp: In function 'void Solve()':
prize.cpp:27:16: error: 'begin' was not declared in this scope
   27 |   for(auto u : m)
      |                ^
prize.cpp:27:16: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from prize.cpp:2:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from prize.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
prize.cpp:27:16: error: 'end' was not declared in this scope
   27 |   for(auto u : m)
      |                ^
prize.cpp:27:16: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from prize.cpp:2:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from prize.cpp:2:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~