제출 #1235367

#제출 시각아이디문제언어결과실행 시간메모리
1235367kaiboy수열 (BOI14_sequence)C++20
0 / 100
26 ms584 KiB
// coached by rainboy #include <algorithm> #include <iostream> using namespace std; const int N = 100000; const long long INF = 0x3f3f3f3f3f3f3f3fLL; long long solve(int *bb, int n, int n_, bool eof) { if (n == 1) { int b = bb[0]; if (b == 1) b = 3; long long ans = 0; for (int d = 1; d < 10; d++) if (b >> d & 1) ans = ans * 10 + d; if (b & 1) ans *= 10; return ans; } if (eof && !bb[0]) { int m = (n + 9) / 10; int *cc = new int[m]; for (int j = 0; j < m; j++) cc[j] = 0; for (int d = 1, j = 0, i = 1; i < n; i++) { int b = bb[i]; if (b >> d & 1) b ^= 1 << d; cc[j] |= b; if (d < 9) d++; else d = 0, j++; } bool yes = !solve(cc, m, n, true); delete[] cc; if (yes) return 0; } long long ans = INF; for (int d_ = 0; d_ < 10; d_++) { if (n_ == 2 && d_ == 9) continue; int m = 1 + (n - (10 - d_) + 9) / 10; int *cc = new int[m]; for (int j = 0; j < m; j++) cc[j] = 0; for (int d = d_, j = 0, i = 0; i < n; i++) { int b = bb[i]; if (b >> d & 1) b ^= 1 << d; cc[j] |= b; if (d < 9) d++; else d = 0, j++; } ans = min(ans, solve(cc, m, n, d_) * 10 + d_); delete[] cc; } return ans; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n; cin >> n; int *bb = new int[n]; for (int i = 0; i < n; i++) { int d; cin >> d; bb[i] = 1 << d; } cout << solve(bb, n, 0, false) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...