Submission #877094

#TimeUsernameProblemLanguageResultExecution timeMemory
877094SorahISACookies (JOI23_cookies)C++17
100 / 100
234 ms237196 KiB
#ifndef SorahISA #define SorahISA #include SorahISA __FILE__ SorahISA const int maxS = 15'000 + 5; void solve() { /** * Score: 100 points * Time Complexity: O(S^2 log S / w) * Space Complexity: O(S^2 log S / w + N^2) **/ int N, S = 0; cin >> N; vector<int> A(N); Prior<pii> pq; for (int i = 0; i < N; ++i) cin >> A[i], S += A[i], pq.ee(A[i], i+1); vector<int> lim(S+1, 0); for (int i = 1; i <= S; ++i) { for (int x : A) lim[i] += min(i, x); } // debug(lim); int M; cin >> M; vector<int> B(M), box(N+1, 0); for (int &x : B) cin >> x, box[x] = 1; bitset<maxS> one; one.set(); Vec<2, bitset<maxS>> dp(S+1); dp[0].resize(N + 1); for (int j = 1; j <= N; ++j) dp[0][j][0] = 1; for (int i = 1; i <= S; ++i) { dp[i].resize(min(N, S/i) + 2); for (int j = min(N, S/i); j >= 1; --j) { if (box[j]) dp[i][j] = (one >> (maxS - lim[i] - 1)) & (dp[i][j+1] | (dp[i-1][j] << j)); else dp[i][j] = (one >> (maxS - lim[i] - 1)) & dp[i][j+1]; } // debug(dp[i]); if (dp[i][1][S]) { print(i); int nowI = i, nowS = S, nowB = 1; while (nowS) { while (!box[nowB] or !dp[nowI-1][nowB][nowS-nowB]) ++nowB; vector<pii> tmp; for (int j = 0; j < nowB; ++j) tmp.eb(pq.top()), pq.pop(); cout << nowB; for (auto [x, id] : tmp) cout << " " << id, pq.ee(x-1, id); cout << "\n"; --nowI, nowS -= nowB; } return; } } print(-1); } void solve_2() { /** * Score: 78 points (Subtask 1,3,4,5) * Time Complexity: O(S^2 log S) * Space Complexity: O(S^2 log S / w) **/ int N, S = 0; cin >> N; vector<pii> A(N); for (int i = 0; i < N; ++i) cin >> A[i].first, A[i].second = i + 1, S += A[i].first; vector<int> lim(S+1, 0); for (int i = 1; i <= S; ++i) { for (auto [x, id] : A) lim[i] += min(i, x); } // debug(lim); int M; cin >> M; vector<int> B(M), box(N+1, 0); for (int &x : B) cin >> x, box[x] = 1; Vec<2, bitset<maxS>> dp(S+1); dp[0].resize(N + 1); for (int j = 1; j <= N; ++j) dp[0][j][0] = 1; for (int i = 1; i <= S; ++i) { dp[i].resize(min(N, S/i) + 1); for (int j = min(N, S/i); j >= 1; --j) { for (int k = lim[i]; k >= 0; --k) { dp[i][j][k] = (j+1 < SZ(dp[i]) ? dp[i][j+1][k] : 0) | ((k >= j and box[j]) ? dp[i-1][j][k-j] : 0); } } // debug(dp[i]); if (dp[i][1][S]) { print(i); int nowI = i, nowS = S, nowB = 1; while (nowS) { while (!box[nowB] or !dp[nowI-1][nowB][nowS-nowB]) ++nowB; sort(RALL(A)); cout << nowB; for (int j = 0; j < nowB; ++j) cout << " " << A[j].second, --A[j].first; cout << "\n"; --nowI, nowS -= nowB; } return; } } print(-1); } void solve_1() { /** * Score: 63 points (Subtask 1,3,4) * Time Complexity: O(NS^2) * Space Complexity: O(NS^2 / w) **/ int N, S = 0; cin >> N; vector<pii> A(N); for (int i = 0; i < N; ++i) cin >> A[i].first, A[i].second = i + 1, S += A[i].first; vector<int> lim(S+1, 0); for (int i = 1; i <= S; ++i) { for (auto [x, id] : A) lim[i] += min(i, x); } // debug(lim); int M; cin >> M; vector<int> B(M), box(N+1, 0); for (int &x : B) cin >> x, box[x] = 1; Vec<2, bitset<maxS>> dp(S+1, N+1); for (int j = 1; j <= N; ++j) dp[0][j][0] = 1; for (int i = 1; i <= S; ++i) { for (int j = N; j >= 1; --j) { for (int k = lim[i]; k >= 0; --k) { dp[i][j][k] = (j < N ? dp[i][j+1][k] : 0) | ((k >= j and box[j]) ? dp[i-1][j][k-j] : 0); } } // debug(dp[i]); if (dp[i][1][S]) { print(i); int nowI = i, nowS = S, nowB = 1; while (nowS) { while (!box[nowB] or !dp[nowI-1][nowB][nowS-nowB]) ++nowB; sort(RALL(A)); cout << nowB; for (int j = 0; j < nowB; ++j) cout << " " << A[j].second, --A[j].first; cout << "\n"; --nowI, nowS -= nowB; } return; } } print(-1); } int32_t main() { fastIO(); int t = 1; // cin >> t; for (int _ = 1; _ <= t; ++_) { // cout << "Case #" << _ << ": "; solve(); } return 0; } #else #ifdef local #define _GLIBCXX_DEBUG 1 #endif #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; #define int int64_t // #define double __float80 using pii = pair<int, int>; template <typename T> using Prior = std::priority_queue<T>; template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; // #define X first // #define Y second #define eb emplace_back #define ef emplace_front #define ee emplace #define pb pop_back #define pf pop_front #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) #define SZ(x) ((int)(x).size()) template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {} }; template <typename T> struct Vec<1, T> : vector<T> { Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {} }; template <class F> inline constexpr decltype(auto) lambda_fix(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } #ifdef local #define fastIO() void() #define debug(...) \ _color.emplace_back("\u001b[31m"), \ fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \ _do(__VA_ARGS__), _color.pop_back(), \ fprintf(stderr, "%s", _color.back().c_str()) #define print(...) \ fprintf(stdout, "%s", "\u001b[36m"), \ _P(__VA_ARGS__), \ fprintf(stdout, "%s", "\u001b[0m") deque<string> _color{"\u001b[0m"}; template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>; template <typename T> concept is_iterable = requires (T _t) {begin(_t);}; template <typename T> inline void _print_err(T &&_t); template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>); template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &); template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t); template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &); template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t); template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu); inline void _do() {cerr << "\n";}; template <typename T> inline void _do(T &&_t) {_print_err(_t), cerr << "\n";} template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) {_print_err(_t), cerr << ", ", _do(_u...);} #else #define fastIO() ios_base::sync_with_stdio(0), cin.tie(0) #define debug(...) void() #define print(...) _P(__VA_ARGS__) #endif inline void _P() {cout << "\n";}; template <typename T> inline void _P(T &&_t) {cout << _t << "\n";} template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) {cout << _t << " ", _P(_u...);} mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int getRand(int L, int R) { if (L > R) swap(L, R); return (int)(rng() % ((uint64_t)R - L + 1) + L); } template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;} template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;} /// below are Fast I/O and _print_err templates /// /* /// Fast I/O by FHVirus /// /// https://fhvirus.github.io/blog/2020/fhvirus-io/ /// #include <unistd.h> const int S = 65536; int OP = 0; char OB[S]; inline char RC() { static char buf[S], *p = buf, *q = buf; return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++; } inline int RI() { static char c; int a; while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1); if (c == '-') { a = 0; while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0'; } else { a = c ^ '0'; while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0'; } return a; } inline void WI(int n, char c = '\n') { static char buf[20], p; if (n == 0) OB[OP++] = '0'; p = 0; if (n < 0) { OB[OP++] = '-'; while (n) buf[p++] = '0' - (n % 10), n /= 10; } else { while (n) buf[p++] = '0' + (n % 10), n /= 10; } for (--p; p >= 0; --p) OB[OP++] = buf[p]; OB[OP++] = c; if (OP > S-20) write(1, OB, OP), OP = 0; } /// Fast I/O by FHVirus /// /// https://fhvirus.github.io/blog/2020/fhvirus-io/ /// */ #ifdef local template <typename T> inline void _print_err(T &&_t) {cerr << _t;} template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) { string _tmp_color = _color.back(); ++_tmp_color[3], _color.emplace_back(_tmp_color); cerr << _color.back() << "["; for (bool _first = true; auto &_x : _t) { if (!_first) cerr << ", "; _print_err(_x), _first = false; } cerr << "]" << (_color.pop_back(), _color.back()); } template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) { string _tmp_color = _color.back(); ++_tmp_color[3], _color.emplace_back(_tmp_color); cerr << _color.back() << "("; _print_err(_tu.first), cerr << ", ", _print_err(_tu.second); cerr << ")" << (_color.pop_back(), _color.back()); return os; } template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) { cerr << ")" << (_color.pop_back(), _color.back()); } template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) { if (!I) { string _tmp_color = _color.back(); ++_tmp_color[3], _color.emplace_back(_tmp_color); cerr << _color.back(); } cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t); } template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) { cerr << ")" << (_color.pop_back(), _color.back()); } template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) { if (!I) { string _tmp_color = _color.back(); ++_tmp_color[3], _color.emplace_back(_tmp_color); cerr << _color.back(); } cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t); } #endif #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...