제출 #1071731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1071731		Ausp3x	비스킷 담기 (IOI20_biscuits)	C++17	9 / 100	102 ms	440 KiB

biscuits

// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "biscuits.h"
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;
typedef __int128     lli;
template<class T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

string getPrintableLli(lli x) {
    string x_str;
    while (x > 0) {
        x_str += '0' + x % 10;
        x /= 10;
    }
    reverse(x_str.begin(), x_str.end());

    return x_str;
}

lng count_tastiness(lng x, vector<lng> A) {
    int K = 60;
    A.resize(K);

    lng total_tastiness = 0; 
    vector<lng> T(K);
    for (int i = 0; i < K; i++) {
        T[i] = 1ll << i;
        total_tastiness += A[i] * T[i];
    }

    if (x > total_tastiness) 
        return 1;
    
    if (total_tastiness <= 100'000) {
        lng ans = 1;
        for (int i = 1; i <= total_tastiness / x; i++) {
            vector<lng> req_cookies(K);
            for (int j = 0; j < K; j++)
                if (i & T[j])
                    req_cookies[j] = x;

            for (int j = K - 1; j > 0; j--)
                req_cookies[j - 1] += 2 * max(req_cookies[j] - A[j], 0ll);
        
            ans += req_cookies[0] <= A[0];
        }

        #ifdef DEBUG
        cout << ans << endl;
        #endif
        #ifndef DEBUG
        return ans;
        #endif
    }

    if (x == 1) {
        for (int i = 0; i < K; i++) 
            for (int j = K - i - 1; j > 0; j--)
                if (A[i] > T[j]) {
                    A[i] -= T[j];
                    A[i + j]++;
                }

        int i_o = 0;
        vector<lng> A_reduced;
        A_reduced.pb(0);
        for (int i = 0; i < K; i++) {
            A_reduced.back() += A[i] * T[i - i_o];
            if (A[i] < 2) {
                A_reduced.pb(0);
                i_o = i + 1; 
            }
        }

        lng ans = 1;
        for (lng a_r : A_reduced) {
            // cout << a_r << ' ';
            ans *= a_r + 1;
        }
        // cout << endl;

        return ans;
    }

    return -1;
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;
    while (t--) {
        int K;
        lng x;
        cin >> K >> x;
        vector<lng> A(K);
        for (lng &a : A)
            cin >> a;

        cout << count_tastiness(x, A) << endl;
    }

    return 0;
}
#endif

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

biscuits.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
biscuits.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
biscuits.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
biscuits.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
In file included from biscuits.cpp:7:
biscuits.h:3:64: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    3 | long long count_tastiness(long long x, std::vector<long long> a);
      |                                                                ^
biscuits.h:3:64: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
biscuits.h:3:64: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
biscuits.cpp:23:29: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   23 | string getPrintableLli(lli x) {
      |                             ^
biscuits.cpp:23:29: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
biscuits.cpp:23:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
biscuits.cpp:23:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
biscuits.cpp:34:41: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   34 | lng count_tastiness(lng x, vector<lng> A) {
      |                                         ^
biscuits.cpp:34:41: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
biscuits.cpp:34:41: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
biscuits.cpp:34:41: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

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