Submission #336655

#	Time	Username	Problem	Language	Result	Execution time	Memory
336655		cheeheng	Packing Biscuits (IOI20_biscuits)	C++14	21 / 100	1087 ms	384 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

long long S = 0;
int k = 0;

long long b[65];
long long a1[65];

bool boleh1(long long y, long long x){
    for(int i = 0; i < k; i ++){
        b[i] = a1[i];
    }
    bool boleh = true;
    for(long long i = 0; i < x; i ++){
        long long rem = y;
        for(int j = k-1; j >= 0; j --){
            long long quotient = min(rem>>j, b[j]);
            b[j] -= quotient;
            rem -= (quotient << j);
        }
        if(rem != 0){
            boleh = false;
            break;
        }
    }
    return boleh;
}

bool boleh2(long long y, long long x){
    bool boleh = true;
    for(int i = 0; i < 60; i ++){
        b[i] = a1[i];
    }
    for(int i = 59; i >= 0; i --){
        if( y&(1LL<<i) ){
            long long rem = x<<i;
            for(int j = min(i, k-1); j >= 0; j --){
                long long quotient = min(rem>>j, b[j]);
                b[j] -= quotient;
                rem -= (quotient << j);
            }
            if(rem != 0){
                boleh = false;
                break;
            }
        }
        if(!boleh){
            break;
        }
    }
    return boleh;
}

long long count_tastiness(long long x, std::vector<long long> a) {
    k = (int)a.size();
    memset(a1, 0, sizeof(a1));
    for(int i = 0; i < k; i ++){
        S += (a[i]<<i);
        a1[i] = a[i];
    }

    if(x == 1){
        for(int i = 0; i < k; i ++){
            b[i] = a[i];
        }
        long long ans2 = 1;

        long long val = 0;
        long long mult = 1;
        long long divider = 1;
        for(int i = 0; i < k; i ++){
            val += a[i]*mult;
            if(val >= x*(2*mult/divider - 1)*divider ){

            }else{
                ans2 *= 1+(val/divider);
                val = 0;

                divider = mult*2;
            }

            mult <<= 1;
        }
        ans2 *= 1+(val/divider);

        //printf("ans2=%lld\n", ans2);
        //assert(ans == ans2);
        return ans2;
    }

    long long ans = 1;
    for(long long y = 1; y <= S/x;){
        bool boleh = true;
        for(int j = 0; j < k; j ++){
            b[j] = a[j];
        }

        long long z = y;

        /*
        for(long long i = 0; i < x; i ++){
            long long rem = y;
            for(int j = k-1; j >= 0; j --){
                long long quotient = min(rem>>j, b[j]);
                b[j] -= quotient;
                rem -= (quotient << j);
            }
            if(rem != 0){
                boleh = false;
                break;
            }
        }*/

        /*
        for(int i = k-1; i >= 0; i --){
            if( y&(1LL<<i) ){
                long long rem = x<<i;
                for(int j = k-1; j >= 0; j --){
                    long long quotient = min(rem>>j, b[j]);
                    b[j] -= quotient;
                    rem -= (quotient << j);
                }
                if(rem != 0){
                    boleh = false;
                    break;
                }
            }
            if(!boleh){
                break;
            }
        }*/
        boleh = boleh2(y, x);
        //assert(boleh1(y, x) == boleh2(y, x));
        //printf("y=%lld x=%lld %d %d\n", y, x, boleh1(y, x), boleh2(y, x));

        if(boleh){
            //printf("y=%lld works\n", y);
            y ++;
        }else{
            long long lsb = y&(-y);
            y += lsb;
            y = y/lsb*lsb;
        }
        ans += boleh;
    }

	return ans;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:100:19: warning: unused variable 'z' [-Wunused-variable]
  100 |         long long z = y;
      |                   ^

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