Submission #941577

#	Time	Username	Problem	Language	Result	Execution time	Memory
941577		shoryu386	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	0 ms	344 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    
    //k books, sum of A
    typedef long long ll;
    
    //x, x+1, x+2, x+3, x+4, x+5... and so on
    
    int extrasum = 0;
    for (int x = 0; x < K; x++){
		extrasum += x;
	}
	
	//we want A <= x*K + extrasum <= 2*A
	//x*K + extrasum >= A
	//x*K >= A-extrasum
	//x >= (A-extrasum)/K
	
	ll target = (A - extrasum)/K + ((A - extrasum)%K != 0);
	//to do: check rounding
	
	if (A - extrasum <= 0) {impossible(); return;}
	
	int l = 1, r = N+1-K, ans = N+1-K;
	
	while (l <= r){
		int m = (l+r)/2;
		
		ll resA = skim(m);
		ll resB = skim(m);
		
		ll lowestCase = resA*K + extrasum;
		ll highestCase = resB*K - extrasum;
		
		bool lowestPass = (lowestCase <= A);
		bool highestPass = (highestCase <= 2LL*A);
		
		if (lowestPass && highestPass){
			
			vector<int> indices;
			for (int x = 0; x < K; x++){
				indices.push_back(m+x);
			}
			answer(indices);
			return;
		}
		else if (!lowestPass && !highestPass){
			impossible();
		}
		else if (lowestPass){
			l = m+1;
		}
		else{
			r = m-1;
		}
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:23:5: warning: unused variable 'target' [-Wunused-variable]
   23 |  ll target = (A - extrasum)/K + ((A - extrasum)%K != 0);
      |     ^~~~~~
books.cpp:28:24: warning: unused variable 'ans' [-Wunused-variable]
   28 |  int l = 1, r = N+1-K, ans = N+1-K;
      |                        ^~~

• 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