oj.uz

Submission #303795

# Submission time Handle Problem Language Result Execution time Memory
303795 2020-09-20T16:14:42 Z alex_velea Packing Biscuits (IOI20_biscuits) C++17
0 / 100
 3 ms 416 KB 
#include <vector>
#include <iostream>
#include <map>
using namespace std;
const int kMaxK = 127;

typedef long long int64;
typedef __int128_t int128;

#define DEBUG if(0)

long long count_tastiness(int64 x, std::vector<int64> a) {
    a.resize(kMaxK, 0);
    int128 target_carry = 0;
    int128 p = 1;
    for (int i = 0; i < (int)a.size(); i += 1) {
        target_carry += a[i] * p;
        p *= 2;
    }

    map<int128, int64> old = { {0, 1} };

    int64 ans = 1;

    int128 global_carry = 0;
    p = 1;
    for (int i = 0; i < kMaxK; i += 1) {
        global_carry += a[i] * p;

        vector<pair<int128, int64>> new_additions;
        for (auto itr = old.rbegin(); itr != old.rend(); itr++) {
            int128 carry = itr->first;
            int64 num = itr->second;

            if (global_carry + carry >= x * p) {
                DEBUG cerr << "Add + for " << i << '\n';
                ans += num;
                new_additions.emplace_back(carry - x * p, num);
            }
        }

        for (auto& itr : new_additions) {
            old[itr.first] += itr.second;
        }

        p *= 2;
        if (target_carry == global_carry) {
            break;
        }
    }

	return ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 35.0

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

Subtask #5
0 / 23.0

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