제출 #306253

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
306253		qpwoeirut	Packing Biscuits (IOI20_biscuits)	C++17	9 / 100	1091 ms	384 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll sub2(ll x, vector<ll> a) {
    //cerr << "a: "; for (int i=0; i<a.size(); ++i) cerr << a[i] << ' '; cerr << endl;

    ll ans = 1;
    for (int i=0; i<a.size(); ++i) {
        if (a[i] >= x) ans <<= 1;
    }
    //cerr << "base: " << ans << endl;

    int cur = 0;
    for (int i=0; i<a.size(); ++i) {
        if (a[i] > x) {
            ++cur;
            a[i+1] += a[i] >> 1;
            a[i] = 0;
        }
        else {
            if (cur > 0) {
                ans += ans >> cur;
            }
            cur = 0;
        }
    }

	return ans;
}

long long count_tastiness(long long x, std::vector<long long> a) {
    a.resize(128, 0);
    //cerr << "a: "; for (int i=0; i<a.size(); ++i) cerr << a[i] << ' '; cerr << endl;
    int add = 0;
    for (int i=0; i<a.size(); ++i) {
        a[i] += add;
        add = max(0LL, (a[i] - x) >> 1);
        a[i] -= add << 1;
    }

    ll ans = 0;
    for (int y=0; y<=100000; ++y) {
        ll carry = 0;
        bool ok = true;
        for (int i=0; i<62; ++i) {
            ll cur = a[i] + carry;
            if (y & (1LL << i)) {
                if (cur < x) {
                    ok = false;
                    break;
                }
                cur -= x;
            }
            carry = cur >> 1;
        }
        if (ok) {
            ++ans;
            //cerr << "y: " << y << '\n';
        }
    }
    
    return ans;
}

/*
2
3 3
5 2 1
3 2
2 1 2

1
5 1
0 1 1 1 2

1
4 1
1 5 2 9

1
5 1
0 0 0 1 0

1
1 1
128
*/

컴파일 시 표준 에러 (stderr) 메시지

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

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