結果
問題 | No.8055 2019(注:異常な難易度です) |
ユーザー |
![]() |
提出日時 | 2019-04-01 18:56:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 182 ms / 2,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 829 ms |
コンパイル使用メモリ | 78,460 KB |
実行使用メモリ | 27,760 KB |
最終ジャッジ日時 | 2024-11-25 22:48:48 |
合計ジャッジ時間 | 4,744 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 91 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; #pragma warning (disable: 4996) long long N, dp[2009][609], t[609]; void getsum(long long dig, long long l, long long r) { for (int i = 0; i <= 600; i++) t[i] = 0; for (int i = 0; i < 2009; i++) { for (int j = 0; j < 609; j++) dp[i][j] = 0; } dp[0][0] = 1; for (int i = 0; i <= dig; i++) { for (int j = 0; j < 609; j++) dp[i + 1][j] = dp[i][j] * 2; for (int j = 0; j < 600; j++) { dp[i + 1][j + 1] += dp[i + 1][j] / 10; dp[i + 1][j] %= 10; } } for (int i = 0; i < dig; i++) { if (l <= i && i <= r) continue; for (int j = 0; j < 600; j++) t[j] += dp[i][j]; } for (int j = 0; j < 600; j++) { t[j + 1] += t[j] / 10; t[j] %= 10; } bool flag = false; for (int i = 600; i >= 0; i--) { if (t[i] >= 1) flag = true; if (flag == true) cout << t[i]; } cout << endl; } void solve(long long NN) { N = NN; for (int i = 1; i <= 2000; i++) { long long E = 1LL * (i - 2) * (i - 1) / 2; E += 1LL; if (N <= E) { vector<pair<int, int>>vec; for (int j = 1; j <= i - 2; j++) { for (int k = j; k <= i - 2; k++) { // 区間 [j, k] について vec.push_back(make_pair(k, -j)); } } vec.push_back(make_pair(-2000, -2000)); sort(vec.begin(), vec.end()); reverse(vec.begin(), vec.end()); getsum(i, -vec[N - 1].second, vec[N - 1].first); return; } else N -= E; } } int main() { long long T; cin >> T; solve(T); return 0; }