Submission #1276348

#TimeUsernameProblemLanguageResultExecution timeMemory
1276348domiPaint By Numbers (IOI16_paint)C++20
100 / 100
834 ms332508 KiB
#include <bits/stdc++.h> #include "paint.h" // #define int long long #define fi first #define se second #define sz(a) (int)((a).size()) #define all(a) (a).begin(), (a).end() #define lsb(x) (x & (-x)) #define vi vector<int> #define YES { cout << "YES" << endl; return; } #define NO { cout << "NO" << endl; return; } using ll = long long; using pii = std::pair<int, int>; using namespace std; int n, k; vector<vector<array<int, 2>>> get_dp(string s, vector<int> c) { vector<vector<array<int, 2>>> dp(n + 5, vector<array<int, 2>>(k + 1, {0, 0})); vector<int>pref(n + 5, 0); s = '$' + s; for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (s[i] == '_'); auto alb = [&](int l, int r) -> int { return (pref[r] - pref[l - 1]) > 0; }; dp[0][0][0] = 1; for (int i = 1; i <= n; ++i) { ///pun alb for (int j = 0; j <= k; ++j) { if (s[i] != 'X' && (dp[i - 1][j][0] || dp[i - 1][j][1])) dp[i][j][0] = 1; } for (int j = 1; j <= k; ++j) { int len = c[j - 1]; int st = i - len + 1; if (st < 1 || alb(st, i) || (st > 1 && s[st - 1] == 'X')) continue; if (dp[st - 1][j - 1][0]) dp[i][j][1] = 1; } } return dp; } string solve_puzzle(string s, vector<int> c) { n = sz(s); k = sz(c); auto sR = s; reverse(all(sR)); auto cR = c; reverse(all(cR)); auto dpL = get_dp(s, c); auto dpR = get_dp(sR, cR); auto get_dpR = [&](int i, int j, int c) -> int{ int idx = n - i + 1; if (idx < 0 || idx > n) return 0; return dpR[idx][j][c]; }; s = '$' + s; vector<int>pref(n + 5, 0LL); for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + (s[i] == '_'); auto alb = [&](int l, int r) -> int { return (pref[r] - pref[l - 1]) > 0; }; vector<int>canW(n + 5); for (int i = 1; i <= n; ++i) { if (s[i] == 'X') continue; for (int j = 0; j <= k && !canW[i]; ++j) { bool left = (dpL[i - 1][j][0] || dpL[i - 1][j][1]); bool right = (get_dpR(i + 1, k - j, 0) || get_dpR(i + 1, k - j, 1)); if (left && right) canW[i] = 1; } } vector<int>mars(n + 5, 0); for (int j = 1; j <= k; ++j) { int len = c[j - 1]; for (int st = 1; st + len - 1 <= n; ++st) { int dr = st + len - 1; if (alb(st, dr) || (st > 1 && s[st - 1] == 'X') || (dr < n && s[dr + 1] == 'X')) continue; if (dpL[st - 1][j - 1][0] && get_dpR(dr + 1, k - j, 0)) { ++mars[st]; --mars[dr + 1]; } } } string ans(n, '?'); for (int i = 1; i <= n; ++i) { mars[i] += mars[i - 1]; if (canW[i] && !mars[i]) ans[i - 1] = '_'; if (!canW[i] && mars[i]) ans[i - 1] = 'X'; } return ans; } // signed main() { // cin.tie(nullptr)->sync_with_stdio(false); // string s; // int k; // cin >> s >> k; // vector<int>c(k); // for (auto &it : c) // cin >> it; // cout << solve_puzzle(s, c); // return 0; // }

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...