# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
69970 | octopuses | Zalmoxis (BOI18_zalmoxis) | C++17 | 396 ms | 15088 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.
//Giorgi Kldiashvili
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define M 1000000007ll
using namespace std;
const int N = 1000020;
int n, k;
int A[N], a[N];
int S, surplus, needed, now;
vector < int > answer;
void go(int x)
{
if(x == 0)
{
answer.push_back(x);
return;
}
if(surplus)
{
surplus --;
go(x - 1);
go(x - 1);
} else
answer.push_back(x);
}
int main()
{
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &a[i]);
A[i] = (1 << a[i]);
}
S = A[1];
needed = 0;
for(int i = 2; i <= n; ++ i)
{
now = A[i] - (S % A[i]);
if(now == A[i]) now = 0;
needed += __builtin_popcount(now);
S += now + A[i];
}
now = (1 << 30) - S;
needed += __builtin_popcount(now);
surplus = k - needed;
answer.push_back(a[1]);
S = A[1];
for(int i = 2; i <= n; ++ i)
{
now = A[i] - (S % A[i]);
if(now == A[i]) now = 0;
for(int j = 0; j < 30; ++ j)
if(now & (1 << j))
go(j);
answer.push_back(a[i]);
S += now + A[i];
}
now = (1 << 30) - S;
for(int j = 0; j < 30; ++ j)
if(now & (1 << j))
go(j);
for(int i = 0; i < answer.size(); ++ i)
printf("%d ", answer[i]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |