| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 813723 | vjudge1 | 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.
#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e6+69;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int a[maxn],m,sum;
deque<int> gg;
//void __attribute__((noreturn)) __attribute__((format(printf, 1, 2))) result(const char *msg, ...)
//{
// va_list args;
// va_start(args, msg);
// vfprintf(stderr, msg, args);
// fprintf(stderr, "\n");
// va_end(args);
// exit(0);
//}
//
//namespace
//{
// int N, K, S, sUsed;
// long long A;
// vector<long long> seq;
//}
//
//void impossible()
//{
// result("Impossible (not checked): %d book(s) skimmed", sUsed);
// exit(0);
//}
//
//long long skim(int pos)
//{
// printf("skim(%d): ", pos);
// if (pos<1 || pos>N) result("Invalid skim");
// printf("%lld\n", seq[pos]);
// sUsed++;
// if (sUsed>S) result("Out of books to skim");
// return seq[pos];
//}
//
//void answer(vector<int> v)
//{
// printf("answer({");
// for(int i = 0; i < (int) v.size(); ++i)
// {
// printf("%d", v[i]);
// if(i + 1 != (int) v.size()) printf(", ");
// }
// printf("})\n");
//
// if ((int) v.size() != K) result("Invalid answer");
// ll sum = 0;
// for(auto x: v) {
// if (x<1 || x>N) result("Invalid answer");
// sum += seq[x];
// }
// if (sum < A || 2*A<sum) result("Wrong answer");
//
// result("Correct: %d book(s) skimmed", sUsed);
// exit(0);
//}
bool check(int mid,int k)
{
a[mid]=skim(mid);
gg.pb(mid);
sum+=a[mid];
while (gg.size()>k)
{
int x=a[gg.front()];
sum-=x;
gg.pop_front();
}
if (sum/gg.size()<= m) return true;
else return false;
}
vector<int> take()
{
vector<int> kk;
while (!gg.empty())
{
kk.pb(gg.front());
gg.pop_front();
}
return kk;
}
void solve(int n,int k,int a,int s)
{
m=(3*a/2)/k;
int l=1,r=n,mid;
while (l<=r)
{
int mid=l+r>>1;
if (check(mid,k)) l=mid+1;
else r= mid-1;
if (gg.size()==k && sum>=a && sum <=2*a)
{
answer(take());
}
}
impossible();
}
//int main()
//{
// if(scanf("%d %d %lld %d", &N, &K, &A, &S) != 4)
// result("Invalid input");
//
// seq.resize(N + 1);
// for(int i = 1; i <= N; ++i) {
// if(scanf("%lld", &(seq[i])) != 1) result("Invalid input");
// if(i>1 && seq[i]<=seq[i-1]) result("Invalid input");
// }
//
// solve(N, K, A, S);
//
// result("No answer");
//}