제출 #916817

#제출 시각아이디문제언어결과실행 시간메모리
916817andrei_iorgulescuBinary Subsequences (info1cup17_binary)C++14
43 / 100
767 ms26824 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 20; const int K = 20000; int cnt[10 * K + 5]; int cnt2[10 * K + 5]; bool found[10 * K + 5]; int a[N + 5]; vector<int>sol[10 * K + 5]; int dp[10 * K + 5]; void afis(int M) { int sumdp = 1,d0 = 0,d1 = 0; int p; for (p = 2; p <= M; p++) { if (a[p] != a[p - 1]) break; } if (p == M + 1) { cnt2[M]++; if (sol[p - 1].size() == 0 or M < sol[p - 1].size()) { sol[p - 1].clear(); for (int i = 1; i <= M; i++) sol[p - 1].push_back(a[i]); } return; } for (int i = 1; i < p; i++) dp[i] = 1; dp[p] = p; if (a[1] == 1) d1 = 1,d0 = p,sumdp = 2 * p - 1; else d1 = p,d0 = 1,sumdp = 2 * p - 1; for (int i = p + 1; i <= M; i++) { if (a[i] == 1) { int j = i - 1; while (j > 0 and a[j] == 0) d1 += dp[j],j--; dp[i] = d1; } else { int j = i - 1; while (j > 0 and a[j] == 1) d0 += dp[j],j--; dp[i] = d0; } if (a[i] == 0) sumdp += d0; else sumdp += d1; if (sumdp > K) return; found[sumdp] = true; } found[sumdp] = true; cnt2[sumdp]++; /*if (sumdp == 5) { for (int i = 1; i <= M; i++) cout << a[i] << ' '; cout << endl; }*/ if (sol[sumdp].size() == 0 or M < sol[sumdp].size()) { sol[sumdp].clear(); for (int i = 1; i <= M; i++) sol[sumdp].push_back(a[i]); } } void bkt(int pos) { if (pos != 1) afis(pos - 1); if (pos == N + 1) return; else { a[pos] = 0; bkt(pos + 1); a[pos] = 1; bkt(pos + 1); } } int sdp,dp0,dp1; void bktsus(int pos,int pz,int sumant) { //cout << pos << ' ' << pz << ' ' << sumant << ' ' << sdp << endl; if (sdp > K) return; cnt[sdp]++; if (pos == 1) { for (int len = 1; len <= K; len++) { sdp = len; dp0 = 1; dp1 = 0; bktsus(pos + 1,len + 1,len); //cout << len << endl; } } else { if (pos % 2 == 1) { int ret_sdp = sdp; int ret_dp1 = dp1; int ret_dp0 = dp0; dp0 += sumant; sdp += dp0; bktsus(pos + 1,pz + 1,dp0); for (int len = 2; sdp <= K; len++) { sdp += dp0; bktsus(pos + 1,pz + len,len * dp0); } sdp = ret_sdp; dp0 = ret_dp0; dp1 = ret_dp1; } else { int ret_sdp = sdp; int ret_dp0 = dp0; int ret_dp1 = dp1; if (pos == 2) dp1 = 1; dp1 += sumant; sdp += dp1; bktsus(pos + 1,pz + 1,dp1); for (int len = 2; sdp <= K; len++) { sdp += dp1; bktsus(pos + 1,pz + len,len * dp1); } sdp = ret_sdp; dp0 = ret_dp0; dp1 = ret_dp1; } } } signed main() { for (int i = 1; i <= N; i++) found[i] = true; bkt(1); bktsus(1,1,0); for (int i = 1; i <= K; i++) cnt[i] = 2 * cnt[i]; /*for (int i = 1; i <= K; i++) if (!found[i]) cout << i << endl;*/ //for (int i = 1; i <= N; i++) // cout << i << ' ' << cnt[i] << ' ' << cnt2[i] << endl; int tc; cin >> tc; while (tc--) { int kk; cin >> kk; cout << cnt[kk] << '\n'; for (auto it : sol[kk]) cout << it << ' '; cout << '\n'; } return 0; }

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

binary.cpp: In function 'void afis(long long int)':
binary.cpp:29:41: 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]
   29 |         if (sol[p - 1].size() == 0 or M < sol[p - 1].size())
      |                                       ~~^~~~~~~~~~~~~~~~~~~
binary.cpp:76:37: 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]
   76 |     if (sol[sumdp].size() == 0 or M < sol[sumdp].size())
      |                                   ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...