結果
問題 |
No.3299 K-th MMA String
|
ユーザー |
![]() |
提出日時 | 2025-10-06 18:38:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 1,030 ms |
コンパイル使用メモリ | 110,600 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-06 18:38:43 |
合計ジャッジ時間 | 2,475 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:45:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 45 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3299.cc: No.3299 K-th MMA String - yukicoder */ #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<bitset> #include<algorithm> #include<numeric> #include<functional> #include<utility> #include<tuple> using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_M = 30; /* typedef */ /* global variables */ int dp0[MAX_M + 1][4], dp1[MAX_M + 1][2]; /* subroutines */ /* main */ int main() { int n, k; scanf("%d%d", &n, &k); k--; dp0[0][3] = 1; int m = 0; for (int i = 0; i < MAX_M; i++) { for (int j = 0; j < 4; j++) { if (dp0[i][j]) { for (int b = 0; b < 2; b++) { int msk = (j << 1) | b, j1 = msk & 3; if (msk == 3) dp1[i + 1][b] += dp0[i][j]; else dp0[i + 1][j1] += dp0[i][j]; } } } for (int b = 0; b < 2; b++) dp1[i + 1][b] += dp1[i][0] + dp1[i][1]; if (dp1[i + 1][0] + dp1[i + 1][1] > k) {m = i + 1; break;} } //printf(" m=%d: %d,%d\n", m, dp1[m][0], dp1[m][1]); for (int i = n; i > m; i--) putchar('A'); for (int i = m, msk = 0, f = 0; i > 0; i--) { msk = (msk << 1) & 7; if (msk == 6) f = 1; int di = f ? (1 << (i - 1)) : dp1[i][0]; if (k < di) putchar('A'); else { putchar('M'); k -= di; msk |= 1; } } putchar('\n'); return 0; }