제출 #421753

#제출 시각아이디문제언어결과실행 시간메모리
421753usachevd0비스킷 담기 (IOI20_biscuits)C++17
0 / 100
1083 ms416 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "biscuits.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& e : v) stream << e << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const ll INF64 = 1e18; ll count_tastiness_stu(ll x, vector<ll> a) { int k = a.size(); ll sum = 0; for (int i = 0; i < k; ++i) sum += (a[i] << i); auto good = [&](ll y) -> bool { vector<ll> b(all(a)); int j = k - 1; for (int i = k - 1; i >= 0; --i) { chkmin(j, i); if ((y >> i) & 1) { ll need = x; for (; j >= 0; --j) { if (b[j] >= need) { b[j] -= need; need = 0; break; } need -= b[j]; b[j] = 0; need *= 2; } if (need) return false; } } return true; }; ll ans = 1; for (ll y = 1; y <= 200000 && x * y <= sum; ++y) { ans += good(y); } return ans; } ll b[60]; ll mem[(int)5e6]; ll count_tastiness(ll x, vector<ll> a) { int k = a.size(); ll sum = 0; for (int i = 0; i < k; ++i) sum += (a[i] << i); ll ans = 0; int tot = 0; for (int i = 0; i < k; ++i) b[i] = a[i]; ll cur = 0; function<void(int, int, int)> brute = [&](int i, int t, int mem_ptr) { if (i == -1) { assert(++tot <= 15e6); // debug(cur); ++ans; return; } ll ans0 = ans; brute(i - 1, t, mem_ptr); ll dans = ans - ans0; ll need = x; int mem_ptr0 = mem_ptr; chkmin(t, i); if (t < i) { if (need > (INF64 >> (i - t)) + 1) t = -1; else need <<= (i - t); } int t0 = t; for (; t >= 0; --t) { mem[mem_ptr++] = b[t]; if (b[t] >= need) { b[t] -= need; need = 0; while (t >= 0 && b[t] == 0) --t; break; } need -= b[t]; b[t] = 0; need *= 2; if (need > INF64) { break; } } if (!need) { if (1 || t < i) { cur ^= 1ll << i; brute(i - 1, t, mem_ptr); cur ^= 1ll << i; } else ans += dans; } chkmax(t, 0); for (; t <= t0; ++t) { b[t] = mem[--mem_ptr]; } }; int t = k - 1; while (t >= 0 && b[t] == 0) --t; brute(59, t, 0); return ans; // ll ans = 1; // for (ll y = 1; y <= 200000 && x * y <= sum; ++y) { // ans += good(y); // } // return ans; } #ifdef LOCAL mt19937 rng(228); ll randll(ll L, ll R) { return rng() % (R - L + 1) + L; } int32_t main() { #ifdef LOCAL freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); /*const ll C = 4; for (int test = 1; ; ++test) { ll x = 1; int k = 2; vector<ll> a(k); for (auto& x : a) x = randll(0, C); if (count_tastiness(x, a) != count_tastiness_stu(x, a)) { cout << "1\n"; cout << x << ' ' << k << '\n'; cout << a << '\n'; exit(0); } if (test % 1000 == 0) debug(test); }/**/ int q; assert(scanf("%d", &q) == 1); vector<int> k(q); vector<long long> x(q); vector<vector<long long>> a(q); vector<long long> results(q); for (int t = 0; t < q; t++) { assert(scanf("%d%lld", &k[t], &x[t]) == 2); a[t] = vector<long long>(k[t]); for (int i = 0; i < k[t]; i++) { assert(scanf("%lld", &a[t][i]) == 1); } } fclose(stdin); for (int t = 0; t < q; t++) { results[t] = count_tastiness(x[t], a[t]); } for (int t = 0; t < q; t++) { printf("%lld\n", results[t]); } fclose(stdout); return 0; } #endif

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

biscuits.cpp:206:6: warning: "/*" within comment [-Wcomment]
  206 |     }/**/
      |       
biscuits.cpp: In lambda function:
biscuits.cpp:124:13: warning: unused variable 'mem_ptr0' [-Wunused-variable]
  124 |         int mem_ptr0 = mem_ptr;
      |             ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...