Submission #1060431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060431		Mihailo	Packing Biscuits (IOI20_biscuits)	C++17	12 / 100	11 ms	3976 KiB

biscuits

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
#define pll pair<long long, long long>
#define MOD 1000000007
typedef long long ll;
using namespace std;
mt19937 mt(time(nullptr));
#include <cassert>
#include <cstdio>

struct node {
    ll ls, rs, lb, v;
    node *right;
    node(): ls(0), rs(0), lb(0), v(0), right(nullptr) {};
};

ll count(node *cur, ll k) {
    ll rez=0;
    if(cur->right==nullptr) {
        if(k<=0) return 1;
        else return 0;
    }
    if(cur->right->v>=k) {
        rez+=cur->rs;
        if(cur->lb!=-1) rez+=count(cur->right, max(k, cur->lb));
    }
    else {
        rez+=count(cur->right, k-cur->right->v);
    }
    return rez;
}

void setl(node *cur, ll k) {
    //cout<<k<<'\n';
    if(cur->right==nullptr) return;
    if(false&&k>cur->right->v) {
        cur->lb=-1;
        cur->ls=0;
        setl(cur->right, k-cur->right->v);
        cur->rs=cur->right->ls+cur->right->rs;
        return;
    }
    if(cur->lb==-1) return;
    cur->lb=max(k, cur->lb);
    cur->ls=count(cur->right, cur->lb);
}

node *create(node *ch, ll v) {
    //cout<<v<<' ';
    node *cur=new node();
    cur->rs=ch->ls+ch->rs;
    ch->v=v;
    cur->right=ch;
    return cur;
}

node *top;
__int128 A[100], X;
ll K=60, zer;

ll count_tastiness(ll x, vector<ll> a) {
    X=x;
    //cout<<"start\n";
    for(int i=0; i<a.size(); i++) A[i]=((__int128)a[i])<<(K+2);
    for(int i=a.size(); i<K; i++) A[i]=0;
    zer=0;
    top=new node();
    top->rs=1;
    for(int i=0; i<K; i++) {
        //cout<<(ll)(A[i])<<' ';
        if(A[i]>=(X<<(K+2))) {
            A[i+1]+=(A[i]-(X<<(K+2)))/2;
            A[i]=X<<(K+2);
        }
        else {
            A[i+1]+=(A[i]%(X<<(K+2-i)));
            A[i]-=(A[i]%(X<<(K+2-i)));
        }
        //cout<<(ll)(A[i])<<' ';
        top=create(top, ((__int128)1)<<i);
        setl(top, zer+(((__int128)1)<<i)-(A[i]/(X<<(K+2-i))));
        zer+=(((__int128)1)<<i)-(A[i]/(X<<(K+2-i)));
    }
    return count(top, 0);
}

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0; i<a.size(); i++) A[i]=((__int128)a[i])<<(K+2);
      |                  ~^~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 21
• Subtask 4: 0 / 35
• Subtask 5: 0 / 23