oj.uz

Submission #1086722

# Submission time Handle Problem Language Result Execution time Memory
1086722 2024-09-11T10:19:24 Z LOLOLO Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 232 ms 16208 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           s     second
#define           f     first
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e6 + 10;
ll sum[40];
multiset <ll> save[40];

void add(ll x, int c) {
    int p = 0;
    while ((ll)1 << (p + 1) <= x) {
        p++;
    }

    if (c == 1) {
        sum[p] += x;
        save[p].insert(x);
    } else {
        sum[p] -= x;
        save[p].erase(save[p].find(x));
    }
}

bool ok() {
    ll cur = 0;
    for (int i = 0; i < 40; i++) {
        if (save[i].empty())
            continue;

        auto it = save[i].begin();
        ll val = *it;
        if (cur + 1 < val)
            return 0;

        if (sz(save[i]) >= 2) {
            it = next(it);
            if (cur + val + 1 < *it)
                return 0;
        }

        cur += sum[i];
    }

    return 1;
}

bool init(int n, ll mx, ll coin[]) {
    for (int i = 0; i < n; i++) {
        add(coin[i], 1);
    }

    return ok();
}

bool is_happy(int c, int n, long long coin[]) {
    for (int i = 0; i < n; ++i) {
        add(coin[i], c);
    }

    return ok();
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 5 ms 1112 KB Output is correct
10 Correct 4 ms 968 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 117 ms 9036 KB Output is correct
7 Correct 123 ms 9044 KB Output is correct
8 Correct 118 ms 9044 KB Output is correct
9 Correct 186 ms 10516 KB Output is correct
10 Correct 226 ms 13136 KB Output is correct
11 Correct 107 ms 13648 KB Output is correct
12 Correct 117 ms 13648 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 5 ms 1112 KB Output is correct
10 Correct 4 ms 968 KB Output is correct
11 Correct 117 ms 9036 KB Output is correct
12 Correct 123 ms 9044 KB Output is correct
13 Correct 118 ms 9044 KB Output is correct
14 Correct 186 ms 10516 KB Output is correct
15 Correct 226 ms 13136 KB Output is correct
16 Correct 107 ms 13648 KB Output is correct
17 Correct 117 ms 13648 KB Output is correct
18 Correct 158 ms 11564 KB Output is correct
19 Correct 184 ms 11348 KB Output is correct
20 Correct 232 ms 14416 KB Output is correct
21 Correct 152 ms 10832 KB Output is correct
22 Correct 133 ms 15712 KB Output is correct
23 Correct 136 ms 16208 KB Output is correct
24 Correct 137 ms 11416 KB Output is correct