oj.uz

Submission #397588

# Submission time Handle Problem Language Result Execution time Memory
397588 2021-05-02T12:38:33 Z qwerasdfzxcl Packing Biscuits (IOI20_biscuits) C++14
12 / 100
 116 ms 844 KB 
#include "biscuits.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<ll> A;
ll X;

map<ll, ll> calc(set<ll> &st, int k){
    if (!k){
        map<ll, ll> ret;
        ret[0] = 1;
        ret[1] = ret[0] + (A[0]>=X);
        return ret;
    }
    ll S = 0;
    for (int i=0;i<=k;i++) S += (1LL<<i)*A[i];
    ll c = S/X, mx1 = (1LL<<k)-1;
    set<ll> tmp;
    if (c<(1LL<<(k+1))) tmp.insert(c-(1LL<<k));
    for (auto &val:st) tmp.insert(val&mx1);
    map<ll, ll> tmp2 = calc(tmp, k-1), ret;
    if (c<(1LL<<(k+1))) ret[c] = tmp2[mx1]+tmp2[c&mx1];
    for (auto &val:st){
        if (val<=mx1) ret[val] = tmp2[val];
        else if (val<=c){
            ret[val] = tmp2[mx1]+tmp2[val&mx1];
        }
        else ret[val] = ret[c];
    }
    return ret;
}

long long count_tastiness(long long x, vector<long long> a) {
    A = a;
    X = x;
    ll S = 0;
    int k = (int)A.size()-1;
    for (;!A[k];k--);
    for (int i=0;i<=k;i++) S += (1LL<<i)*A[i];
    //printf(" %d ", k);
    if (!k) return S/x+1;
    if (k<0) return 1;
    ll mx = (1LL<<k)-1, q = (A[k]-1)/x+1;
    ll sr = (S/x)&mx;
    set<ll> tmp;
    tmp.insert(mx);
    tmp.insert(sr);
    map<ll, ll> M = calc(tmp, k-1);
    //printf("%lld %lld\n", M[mx], M[sr]);
    ll ans = M[mx]*q;
    ans += ((S/x)/(1LL<<k)+1-q)*M[mx];
    ans -= M[mx] - M[sr];
    return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 204 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 116 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Halted 0 ms 0 KB -