| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 464021 | AriaH | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/** work as hard as you can and keep the first place **/
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;
ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }
map < ll, ll > mp;
/*ll skim(int i)
{
return 1;
}*/
ll ask(int i)
{
if(mp.count(i))
{
return mp[i];
}
return mp[i] = skim(i);
}
/*void answer(vector < int > vec)
{
}
void impossible()
{
}
*/
void solve(int n, int k, ll A, int s)
{
mp.clear();
int d = 0, up = n + 1;
while(up - d > 1)
{
int mid = (up + d) >> 1;
if(ask(mid) < A) d = mid;
else up = mid;
}
if(up > n) up --;
if(up < k) impossible();
vector < pll > vec;
for(int i = 1; i <= min(k, up - k); i ++)
{
vec.push_back(Mp(ask(i), i));
}
for(int i = up - k + 1; i <= up; i ++)
{
vec.push_back(Mp(ask(i), i));
}
sort(all(vec));
int sz = SZ(vec);
for(int mask = 0; mask < 1 << sz; mask ++)
{
if(__builtin_popcount(mask) != k) continue;
ll sum = 0;
for(int i = 0; i < sz; i ++)
{
if(mask >> i & 1)
{
sum += vec[i].F;
}
}
if(A <= sum && sum <= 2ll * A)
{
vector < int > ret;
for(int i = 0; i < sz; i ++)
{
if(mask >> i & 1) ret.push_back(vec[i].S);
}
answer(ret);
return;
}
}
impossible();
}
int main()
{
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/