이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
// int skim(int x){
// cout<<"skim : "<<x<<"\n";
// cin>>x;
// return x;
// }
// void impossible(){
// cout<<"IMPOSSIBLE\n";
// }
// void answer(vector<int> v){
// cout<<"answer : ";
// for(auto x : v) cout<<x<<" ";
// cout<<"\n";
// }
void solve(int n, int k, ll a, int s){
map<int, ll> mp;
auto get = [&](int x) -> ll {
if(mp[x]) return mp[x];
return mp[x] = skim(x);
};
// find first > A
int l = 1, r = n + 1;
while(l + 1 < r){
int m = (l + r) / 2;
ll x = get(m);
if(x > a) r = m;
else l = m;
}
if(r < k){
impossible();
}
ll ttl = 0;
for(int i = 1; i <= k; i++) ttl += get(i);
if(ttl > 2 * a){
impossible();
}
if(ttl >= a){
vector<int> ans(k);
iota(ans.begin(), ans.end(), 1);
answer(ans);
}
if(r <= n){
if(ttl - get(k) + get(r) <= 2 * a){
vector<int> ans(k - 1);
iota(ans.begin(), ans.end(), 1);
ans.pb(r);
answer(ans);
}
}
if(r <= 2 * k){
for(int i = k + 1; i < r; i++){
ttl += get(i);
ttl -= get(i - k);
if(ttl >= a){
vector<int> ans(k);
iota(ans.begin(), ans.end(), i - k + 1);
answer(ans);
}
}
impossible();
}
for(int i = r - k; i < r; i++){
ttl += get(i);
ttl -= get(i - (r - k) + 1);
if(ttl >= a){
vector<int> ans;
for(int j = i - (r - k) + 2; j <= k; j++) ans.pb(j);
for(int j = r - k; j <= i; j++) ans.pb(j);
answer(ans);
}
}
impossible();
}
// signed main(void){
// int n, k, a, s;
// cin>>n>>k>>a>>s;
// solve(n, k, a, s);
// }
# | 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... |