Submission #943044

#	Time	Username	Problem	Language	Result	Execution time	Memory
943044		theghostking	A Difficult(y) Choice (BOI21_books)	C++17	10 / 100	1 ms	1112 KiB

books

#include <bits/stdc++.h>
 
#include "books.h"
 
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
 
void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    /*
    if (skim(2) == 42) {
        impossible();
    } else {
        answer({1, 3});
    }*/
    //head must be <= floor(A/K)
    vector<long long> dis(N+1, -1);
    int lo = 1;
	int hi = N;
	int mid;
	long long tgt = A/K;
	int bst = N;
	//cout << tgt << '\n';
	while (lo <= hi){
		mid = (lo+hi)/2;
		long long vv;
		if (dis[mid] == -1){
			vv = skim(mid);
			dis[mid] = vv;
		}
		else{
			vv = dis[mid];
		}
		if (vv >= tgt){
			bst = min(bst,mid);
			hi = mid-1;
		}
		else{
			lo = mid+1;
		}
	}
	//cout << bst << '\n';
	//ok head found
	
	for (int i = max(1,bst-K); i <= min(N,bst+K); i++){
		if (dis[i] == -1){
			dis[i] = skim(i);
		}
	}/*
	vector<int> ck;
	int cr = 0;
	for (int i = bst; i<=min(N,bst+K-1); i++){
		ck.push_back(dis[i]);
		cr += dis[i];
	}
	if (cr >= A && cr <= 2*A){
		answer(ck);
	}
	else{
		impossible();
	}*/
	//now check
	for (int i = 0; i<=N; i++){
		//cout << dis[i] << " ";
	}
	//cout << '\n';
	for (int i = max(1,bst-K); i<= min(N,bst+K); i++){
		long long sm = 0;
		vector<int> pot;
		for (int j = i; j<=min(N,i+K-1); j++){
			sm += dis[j];
			pot.push_back(j);
		}
		//cout << sm << '\n';
		for (auto u : pot){
			//cout << u << " ";
		}
		//cout << '\n';
		if ((sm >= A) && (sm<=2*A)){
			answer(pot);
		}
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:83:13: warning: unused variable 'u' [-Wunused-variable]
   83 |   for (auto u : pot){
      |             ^

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