Submission #476752

#TimeUsernameProblemLanguageResultExecution timeMemory
476752SamAndSequence (BOI14_sequence)C++17
25 / 100
159 ms1688 KiB
#include <bits/stdc++.h> using namespace std; #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define fi first #define se second typedef long long ll; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); mt19937 rnf(2106); const ll INF = 1000000009000000009; ll rec(vector<int> v) { if (v.empty()) return 1; if (sz(v) == 1) { ll ans = 0; if (!(v[0] & 1)) { for (int i = 0; i < 10; ++i) { if ((v[0] & (1 << i))) ans = (ans * 10 + i); } } else { bool z = false; for (int i = 1; i < 10; ++i) { if ((v[0] & (1 << i))) { ans = (ans * 10 + i); if (!z) { z = true; ans = (ans * 10); } } } if (!z) ans = 10; } return ans; } ll ans = INF; for (int s = 0; s < 10; ++s) { int x = s; vector<int> u = v; vector<int> nv; int j = 0; for (int i = 0; i < sz(u); ++i) { u[i] = (u[i] & (((1 << 10) - 1) ^ (1 << x))); if (x == 9) { int y = 0; while (j <= i) y |= u[j++]; nv.push_back(y); } x = (x + 1) % 10; } { int y = 0; while (j < sz(u)) y |= u[j++]; if (y) nv.push_back(y); } if (sz(v) == 2 && sz(nv) == 2 && v[0] == nv[0] && v[1] == nv[1]) continue; ans = min(ans, rec(nv) * 10 + s); } return ans; } void solv() { int n; cin >> n; vector<int> v; while (n--) { int x; cin >> x; v.push_back((1 << x)); } ll ans = rec(v); cout << ans << "\n"; } int main() { #ifdef SOMETHING freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); #endif // SOMETHING ios_base::sync_with_stdio(false), cin.tie(0); int tt = 1; //cin >> tt; while (tt--) solv(); 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...