Jamie and Binary Sequence (changed after round) (CodeForces 916B)
Jamie and Binary Sequence (changed after round) (CodeForces 916B)
time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output
Problem Description
Jamie is preparing a Codeforces round. He has got an idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:
Find k integers such that the sum of two to the power of each number equals to the number n and the largest integer in the answer is as small as possible. As there may be multiple answers, you are asked to output the lexicographically largest one.
To be more clear, consider all integer sequence with length k (a1, a2, ..., ak) with . Give a value to each sequence. Among all sequence(s) that have the minimum y value, output the one that is the lexicographically largest.
For definitions of powers and lexicographical order see notes.
Input
The first line consists of two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 105) — the required sum and the length of the sequence.
Output
Output "No" (without quotes) in a single line if there does not exist such sequence. Otherwise, output "Yes" (without quotes) in the first line, and k numbers separated by space in the second line — the required sequence.
It is guaranteed that the integers in the answer sequence fit the range [ - 1018, 1018].
Examples
Input
23 5
Output
Yes 3 3 2 1 0
Input
13 2
Output
No
Input
1 2
Output
Yes -1 -1
思路
官方的标程错了，以下是错解，很容易想到。
用堆维护最大的指数，没凑到k位的话就把最大的指数p pop掉，再push进两个p-1,直到刚好凑到第k位。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define LL long long
priority_queue<int> S;
int main(){
LL n,k,pos=0;
scanf("%I64d %I64d",&n,&k);
int Count=-1;
while(n){
++Count;
if(n&1) S.push(Count);
n>>=1;
}
pos=S.size();
if(pos>k){printf("No\n");return 0;}
while(pos<k){
int mid=S.top();
S.pop();
S.push(mid-1);
S.push(mid-1);
++pos;
}
printf("Yes\n");
while(!S.empty()){
printf("%d ",S.top());
S.pop();
}
printf("\n");
return 0;
}