結果
問題 | No.1630 Sorting Integers (Greater than K) |
ユーザー |
![]() |
提出日時 | 2023-05-04 14:42:08 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 1,853 bytes |
コンパイル時間 | 7,030 ms |
コンパイル使用メモリ | 141,692 KB |
実行使用メモリ | 5,304 KB |
最終ジャッジ日時 | 2024-11-22 07:18:43 |
合計ジャッジ時間 | 3,731 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 22 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; int C[10]; int N; string K; string f(int d) { string res = ""; int CC[10]; memcpy(CC, C, sizeof(C)); bool is_over = false; for (int i = 1; i <= N; ++i) { int v = K[i - 1] - '0'; if (i < d) { if (CC[v] > 0) { CC[v]--; res += to_string(v); } else { return res; } } else if (not is_over) { bool found = false; for (int j = v + 1; j <= 9 && not found; ++j) { if (CC[j] == 0) continue; found = true; CC[j]--; res += to_string(j); } if (not found) { if (CC[v] > 0 && i < N) { CC[v]--; res += to_string(v); } else { return res; } } else { is_over = true; } } else { for (int j = 1; j <= 9; ++j) { if (CC[j] == 0) continue; CC[j]--; res += to_string(j); break; } } } return res; } int main() { cin >> N >> K; for (int i = 1; i <= 9; ++i) { cin >> C[i]; } if (N < K.size()) { cout << -1 << endl; return 0; } else if (N > K.size()) { string ans = ""; for (int i = 1; i <= 9; ++i) { for (int j = 0; j < C[i]; ++j) { ans += to_string(i); } } cout << ans << endl; return 0; } if (f(1).size() != N) { cout << -1 << endl; } else { int ok = 1; int ng = N; while (abs(ok - ng) >= 2) { int d = (ok + ng) / 2; string res = f(d); if (res.size() == N) { ok = d; } else { ng = d; } } cout << f(ok) << endl; } return 0; }