제출 #917214

#제출 시각아이디문제언어결과실행 시간메모리
917214andrei_iorgulescuBinary Subsequences (info1cup17_binary)C++14
43 / 100
842 ms68220 KiB
#include <bits/stdc++.h> using namespace std; const int N = 26; const int K = 100000; int a[N + 5]; vector<int>sol[10 * K + 5]; int dp0,dp1,sumdp; void afis(int M) { 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,int pz,int sumant) { if (pos != 1) afis(pz - 1); if (pz == N + 1) return; else { if (pos & 1) { if (pos == 1) { dp0 = 1; dp1 = 1; for (int lung = 1; lung <= N; lung++) { a[pz + lung - 1] = 0; sumdp = lung; bkt(pos + 1,lung + 1,lung); } } else { dp0 += sumant; for (int lung = 1; lung <= N - pz + 1; lung++) { a[pz + lung - 1] = 0; sumdp += dp0 * lung; bkt(pos + 1,pz + lung,dp0 * lung); sumdp -= dp0 * lung; } dp0 -= sumant; } } else { dp1 += sumant; for (int lung = 1; lung <= N - pz + 1; lung++) { a[pz + lung - 1] = 1; sumdp += dp1 * lung; bkt(pos + 1,pz + lung,dp1 * lung); sumdp -= dp1 * lung; } dp1 -= sumant; } } } int phi[1000005]; const int NMAX = 1e6 + 2; void prec_phi() { for (int i = 1; i <= NMAX; i++) phi[i] = i; for (int i = 2; i <= NMAX; i++) if (phi[i] == i) for (int j = i; j <= NMAX; j += i) phi[j] = phi[j] * (i - 1) / i; } signed main() { //for (int i = 1; i <= N; i++) // found[i] = true; bkt(1,1,0); //bktsus(1,1,0); prec_phi(); /*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 << phi[kk + 2] << '\n'; for (auto it : sol[kk]) cout << it << ' '; cout << '\n'; } return 0; }

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

binary.cpp: In function 'void afis(int)':
binary.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     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...