Submission #772300

#	Time	Username	Problem	Language	Result	Execution time	Memory
772300		tolbi	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1104 KiB

books

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz!..
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& is, pair<X,Y> &pr){return is>>pr.first>>pr.second;}
template<typename X, size_t Y> istream& operator>>(istream& is, array<X,Y> arr){for (auto &it : arr) is>>it; return is;}
template<typename T> istream& operator>>(istream& is, vector<T> arr){for (auto &it : arr) is>>it; return is;}
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define endl '\n'
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vint(x) vector<int> x
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
void impossible();
void answer(vector<int32_t> v);
long long skim(int32_t pos);
vector<int> convert(deque<int> dq){
	vector<int> aa;
	while (dq.size()) aa.push_back(dq.back()),dq.pop_back();
	return aa;
}
long long fiss;
bool fits(long long num){
	return (num>=fiss && num<=fiss*2);
}
void solve(int n, int k, long long a, int s){
	fiss=a;
	int l = 1, r = n;
	long long cr = skim(n);
	long long pos = n+1;
	long long hayd=-23;
	if (cr>=a){
		while (l<r){
			int mid = l+(r-l)/2;
			long long crr = skim(mid);
			if (crr>=a){
				r=mid;
			}
			else {
				l=mid+1;
			}
		}
		pos=r;
		hayd=skim(pos);
	}
	vector<long long> deg(n+1);
	vector<long long> bas;
	vector<long long> son;
	if (pos<k) impossible();
	for (int i = 0; i < k; i++){
		if (i+1>n || i+1<1 || pos-i-1<1 || pos-i-1>n) continue;
		deg[i+1]=skim(i+1);
		deg[pos-i-1]=skim(pos-i-1);
		bas.push_back(i+1);
		son.push_back(pos-i-1);
	}
	deque<int> crarr;
	long long somma = 0;
	for (int i = 0; i < k-1; ++i)
	{
		crarr.push_back(bas[i]);
		somma+=deg[bas[i]];
	}
	if (hayd!=-23){
		if (somma+hayd>=a && somma+hayd<=2*a){
			vector<int> ans;
			while (crarr.size()) ans.push_back(crarr.back()),crarr.pop_back();
			ans.push_back(pos);
			answer(ans);
		}
	}
	crarr.push_back(bas.back());
	somma+=deg[bas.back()];
	if (fits(somma)) answer(convert(crarr));
	for (int i = 0; i < k; i++){
		somma-=deg[crarr.front()];
		crarr.pop_front();
		somma+=deg[son[i]];
		crarr.push_back(son[i]);
		if (fits(somma)) answer(convert(crarr));
	}
	impossible();
}

Compilation message (stderr)

books.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

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