Submission #476795

#TimeUsernameProblemLanguageResultExecution timeMemory
476795SamAndSequence (BOI14_sequence)C++17
100 / 100
459 ms1720 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) { while (!v.empty() && v.back() == 0) v.pop_back(); if (v.empty()) return 0; 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; ll yans = rec(nv); if (s == 0 && yans == 0) yans = 1; ans = min(ans, yans * 10 + s); } { int s = 0; int x = s; vector<int> u = v; vector<int> nv; int j = 0; for (int i = 0; i < sz(u); ++i) { if (i > 0) 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])) { ll yans = rec(nv); ans = min(ans, yans * 10 + s); } } return ans; } bool stg(ll ans, vector<int> v) { bool z = true; int x = ans; for (int i = 0; i < sz(v); ++i) { bool zz = false; int y = x; while (y) { if ((1 << y % 10) == v[i]) { zz = true; break; } y /= 10; } if (!zz) { z = false; break; } ++x; } return z; } 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); /*for (int l = 1; l <= 1000; ++l) { for (int r = l; r <= l + 20; ++r) { vector<int> v; for (int i = l; i <= r; ++i) { int x = i; vector<int> vx; while (x) { vx.push_back(x % 10); x /= 10; } v.push_back((1 << vx[rnf() % sz(vx)])); } ll ans = rec(v); if (!ans) { ans = 1; while (1) { if (stg(ans, v)) break; ans *= 10; } } if (ans > l) { cout << "WA0\n"; cout << l << ' ' << r << "\n"; cout << ans << "\n"; rec(v); return 0; } else if (!stg(ans, v)) { cout << "WA1\n"; cout << l << ' ' << r << "\n"; cout << ans << "\n"; rec(v); return 0; } } } cout << "OK\n"; return 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...