oj.uz

Submission #69970

# Submission time Handle Problem Language Result Execution time Memory
69970 2018-08-22T07:18:40 Z octopuses Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 396 ms 15088 KB 
//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

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < answer.size(); ++ i)
                  ~~^~~~~~~~~~~~~~~
zalmoxis.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &k);
   ~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 14636 KB Output is correct
2 Correct 242 ms 14920 KB Output is correct
3 Correct 231 ms 14920 KB Output is correct
4 Correct 243 ms 14920 KB Output is correct
5 Correct 257 ms 14964 KB Output is correct
6 Correct 304 ms 14964 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 14964 KB Output is correct
2 Correct 346 ms 14964 KB Output is correct
3 Correct 271 ms 15088 KB Output is correct
4 Correct 229 ms 15088 KB Output is correct
5 Correct 234 ms 15088 KB Output is correct
6 Correct 245 ms 15088 KB Output is correct
7 Correct 245 ms 15088 KB Output is correct
8 Correct 282 ms 15088 KB Output is correct
9 Correct 343 ms 15088 KB Output is correct
10 Correct 174 ms 15088 KB Output is correct
11 Correct 173 ms 15088 KB Output is correct
12 Correct 120 ms 15088 KB Output is correct
13 Correct 111 ms 15088 KB Output is correct
14 Correct 104 ms 15088 KB Output is correct