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 <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef long long ll;
ll A[(int)(1e5 + 500)];
vi v;
ll pitaj(int x){
if(A[x]) return A[x];
A[x] = skim(x + 1);
v.PB(x);
return A[x];
}
bool cmp(int i, int j){
return A[i] < A[j];
}
vi nadi(int n, int k, ll L){
sort(v.begin(), v.end(), cmp); vi ret;
for(int i = 0;i + k <= (int)v.size();i++){
ll cur = 0;
for(int j = 0;j < k;j++)
cur += A[v[i + j]];
if(L <= cur && cur <= 2LL * L){
for(int j = 0;j < k;j++)
ret.PB(v[i + j]);
return ret;
}
}
for(;(int)v.size() >= k;v.pop_back()){
for(int i = 0;i <= k;i++){
ll cur = 0;
for(int j = 0;j < i;j++)
cur += A[v[j]];
for(int j = 0;j < k - i;j++)
cur += A[v[(int)v.size() - j - 1]];
if(L <= cur && cur <= 2LL * L){
for(int j = 0;j < i;j++)
ret.PB(v[j]);
for(int j = 0;j < k - i;j++)
ret.PB(v[(int)v.size() - j - 1]);
return ret;
}
}
}
return ret;
}
void solve(int n, int k, ll L, int S) {
//printf("n = %d k = %d L = %lld S = %d\n", n, k, L, S);
int pref = -1;
for(int i = 18;i >= 0;i--){
if(pref + (1 << i) < n && pitaj(pref + (1 << i)) <= L)
pref += (1 << i);
}
pref++; pitaj(pref);
for(int i = 0;i < k;i++)
pitaj(i);
//printf("tu sam pref = %d\n", pref);
for(int i = 0;i < k && pref - i - 1 >= 0;i++)
pitaj(pref - i - 1);
vi ans = nadi(n, k, L);
if((int)ans.size() == 0)
impossible();
for(int &x : ans) x++;
answer(ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |