제출 #400773

#제출 시각아이디문제언어결과실행 시간메모리
400773REALITYNB비스킷 담기 (IOI20_biscuits)C++14
9 / 100
1081 ms332 KiB
#include <bits/stdc++.h> #include "biscuits.h" #define int long long using namespace std; int sub1(int k , vector<int> a){ int ans = 0 ; int n = 60 ; while(a.size()!=n+1) a.push_back(0) ; for(int target=0;target<=100000;target++){ vector<int>b=a; bool flg =1 ; for(int i=0;i<n;i++){ if((1LL<<i)&target){ if(b[i]<k){ flg=0 ; break ; } b[i]-=k; b[i+1]+=b[i]/2 ; } else b[i+1]+=b[i]/2 ; } ans+=flg; } return ans ; } int count_tastiness(int k,vector<int> a){ if(k!=1) return sub1(k,a) ; int n =120 ; while(n!=a.size()) a.push_back(0) ; vector<int> dp(n+1); dp[n]=1; for(int i=n-1;i>-1;i--){ int sum = 0 ; vector<int> b=a; int stop = i+1; for(int j=i;j<n;j++){ if(b[j]>1){ b[j+1]+=b[j]/2; if(b[j]&1) b[j]=1; else b[j]=0; stop=j+2; } else break ; } if(a[i]==0) { dp[i]+=dp[i+1] ; continue ; } vector<int> in ; for(int j=i;j<stop;j++) if(b[j]) in.push_back(j) ; for(int j=1;j<in.size();j++) dp[i]+=dp[stop]*(1LL<<(in[j-1]-i)); dp[i]+=dp[stop]; dp[i]+=dp[stop]*(1<<(in.back()-i)) ; } return dp[0] ; } #define ll long long long long ccount_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; } /*int main(){ cout << count_tastiness(1,{3,1,2,1,0,1}) << " "<< ccount_tastiness(1,{3,1,2,1,0,1}) << endl ; }*/

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

biscuits.cpp: In function 'long long int sub1(long long int, std::vector<long long int>)':
biscuits.cpp:8:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
    8 |     while(a.size()!=n+1) a.push_back(0) ;
      |           ~~~~~~~~^~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:32:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(n!=a.size()) a.push_back(0) ;
      |           ~^~~~~~~~~~
biscuits.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=1;j<in.size();j++)
      |                     ~^~~~~~~~~~
biscuits.cpp:36:13: warning: unused variable 'sum' [-Wunused-variable]
   36 |         int sum = 0 ;
      |             ^~~
biscuits.cpp: In function 'long long int ccount_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:66:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0; i<a.size(); ++i) {
      |                   ~^~~~~~~~~
#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...