Submission #1198265

#TimeUsernameProblemLanguageResultExecution timeMemory
1198265GabpPaint By Numbers (IOI16_paint)C++20
32 / 100
1 ms328 KiB
#include<bits/stdc++.h> #include"paint.h" using namespace std; string solve_puzzle(string s, vector<int> c) { int n = s.size(); int k = c.size(); vector<int> pref(n + 1, 0); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + (s[i] == '_'); } auto sum = [&](int l, int r) -> int { return pref[r + 1] - pref[l]; }; vector<vector<bool>> dp1(n + 2, vector<bool>(k + 1, false)); vector<vector<bool>> dp2 = dp1; dp1[0][0] = true; for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { if (i != n && s[i] == 'X') continue; if (dp1[i][j]) dp1[i + 1][j] = true; else if (j > 0) { int cnt = c[j - 1]; if (i < cnt) continue; if (sum(i - cnt, i - 1)) continue; if (dp1[i - cnt][j - 1]) dp1[i + 1][j] = true; } } } dp2[n][0] = true; for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= k; j++) { if (s[i] == 'X') continue; if (dp2[i + 1][j]) dp2[i][j] = true; else if (j > 0) { int cnt = c[k - j]; if (n - i - 1 < cnt) continue; if (sum(i + 1, i + cnt)) continue; if (dp2[i + cnt + 1][j - 1]) dp2[i][j] = true; } } } vector<bool> white(n + 1, false); vector<int> diff(n + 1, 0); for (int i = 0; i <= n; i++) { if (i != n && s[i] != '.') continue; for (int j = 0; j <= k; j++) { if (!dp1[i + 1][j] || !dp2[i][k - j]) continue; white[i] = true; if (j == 0) continue; int cnt = c[j - 1]; if (i >= cnt && sum(i - cnt, i - 1) == 0) { diff[i - cnt]++; diff[i]--; } } } for (int i = 1; i <= n; i++) diff[i] += diff[i - 1]; string ans = s; for (int i = 0; i < n; i++) { if (ans[i] != '.') continue; assert(diff[i] || white[i]); if (diff[i] && white[i]) ans[i] = '?'; else if (diff[i]) ans[i] = 'X'; else ans[i] = '_'; } return ans; }

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...