Submission #817417

#	Time	Username	Problem	Language	Result	Execution time	Memory
817417		MohamedAhmed04	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	2000 KiB

books

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

using namespace std;

const int MAX = 1e5 + 10 ;

long long arr[MAX] ;

long long query(int idx)
{
	if(arr[idx] == -1)
		arr[idx] = skim(idx) ;
	return arr[idx] ;
}

void solve(int n, int k, long long a, int s) 
{
	memset(arr , -1 , sizeof(arr)) ;
	long long sum = 0 ;
	for(int i = 1 ; i <= k-1 ; ++i)
		arr[i] = skim(i) , sum += arr[i] ;
	int l = k , r = n ;
	int idx = l ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(sum + query(mid) <= 2 * a)
			idx = mid , l = mid+1 ;
		else
			r = mid-1 ;
	}
	query(idx) ;
	sum += arr[idx] ;
	if(sum > 2*a)
	{
		impossible() ;
		return ;
	}
	else if(sum >= a)
	{
		vector<int>ans ;
		for(int i = 1 ; i <= k-1 ; ++i)
			ans.push_back(i) ;
		ans.push_back(idx) ;
		answer(ans) ;
		return ;
	}
	int cur = k-1 ;
	for(int i = idx-1 ; i >= 1 && cur > 0 ; --i)
	{
		sum += query(i) ;
		sum -= query(cur) , --cur ;
		assert(sum <= 2*a) ;
		if(sum >= a)
		{
			vector<int>ans ;
			for(int j = 1 ; j <= cur ; ++j)
				ans.push_back(i) ;
			for(int j = i ; j <= idx ; ++j)
				ans.push_back(j) ;
			long long sum2 = 0 ;
			for(auto &j : ans)
				sum2 += j ;
			assert(ans.size() == k && sum2 >= a && sum2 <= 2*a) ;
			answer(ans) ;
			return ;
		}
	}
	impossible() ;
	return ;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from books.cpp:1:
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:65:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |    assert(ans.size() == k && sum2 >= a && sum2 <= 2*a) ;
      |           ~~~~~~~~~~~^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20