oj.uz

Submission #474654

# Submission time Handle Problem Language Result Execution time Memory
474654 2021-09-19T09:43:04 Z cpp219 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 438 ms 16068 KB 
#include<bits/stdc++.h>
#include <happiness.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;

multiset<ll> s[45];
ll bucket[45];

void Add(ll cond,ll x){
    ll now = 1,cur = 0;
    while(now < x) now *= 2,cur++;
    if (cond > 0) s[cur].insert(x);
    else s[cur].erase(s[cur].find(x));
    bucket[cur] += x*cond;
}

bool chk(){
    ll sum = 0;
    for (ll i = 0;i <= 40;i++) if (s[i].size()){
        ll now = *s[i].begin();
        if (sum + 1 < now) return 0;
        if (s[i].size() > 1 && sum + now + 1 < *next(s[i].begin())) return 0;
        sum += bucket[i];
    }
    return 1;
}

bool init(int coinsCount,ll maxCoinSize,ll coins[]){
    for (ll i = 0;i < coinsCount;i++) Add(1,coins[i]);
    return chk();
}

bool is_happy(int event, int coinsCount,ll coins[]){
    for (ll i = 0;i < coinsCount;i++) Add(event,coins[i]);
    return chk();
}
/*
int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }

}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

happiness.cpp:55:1: warning: "/*" within comment [-Wcomment]
   55 | /* stuff you should look for
      |  
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 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 7 ms 1016 KB Output is correct
9 Correct 7 ms 972 KB Output is correct
10 Correct 6 ms 1008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 194 ms 9012 KB Output is correct
7 Correct 227 ms 9056 KB Output is correct
8 Correct 201 ms 9052 KB Output is correct
9 Correct 289 ms 10368 KB Output is correct
10 Correct 438 ms 12920 KB Output is correct
11 Correct 237 ms 13588 KB Output is correct
12 Correct 206 ms 13620 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 7 ms 1016 KB Output is correct
9 Correct 7 ms 972 KB Output is correct
10 Correct 6 ms 1008 KB Output is correct
11 Correct 194 ms 9012 KB Output is correct
12 Correct 227 ms 9056 KB Output is correct
13 Correct 201 ms 9052 KB Output is correct
14 Correct 289 ms 10368 KB Output is correct
15 Correct 438 ms 12920 KB Output is correct
16 Correct 237 ms 13588 KB Output is correct
17 Correct 206 ms 13620 KB Output is correct
18 Correct 243 ms 11404 KB Output is correct
19 Correct 266 ms 11396 KB Output is correct
20 Correct 403 ms 14460 KB Output is correct
21 Correct 236 ms 10904 KB Output is correct
22 Correct 239 ms 15744 KB Output is correct
23 Correct 232 ms 16068 KB Output is correct
24 Correct 224 ms 11192 KB Output is correct