Submission #598961

#TimeUsernameProblemLanguageResultExecution timeMemory
598961snasibov05Paint By Numbers (IOI16_paint)C++14
32 / 100
1 ms340 KiB
#include "paint.h" #include <cstdlib> #include <bits/stdc++.h> using namespace std; const int mxn = 2e5 + 5, mxk = 1e2 + 5; bool pref[mxn][mxk][2]; bool suf[mxn][mxk][2]; string solve_puzzle(string s, vector<int> c) { int n = s.size(); int k = c.size(); s = ' ' + s; vector<int> prefw(n+1); for (int i = 1; i <= n; ++i){ prefw[i] = prefw[i-1] + (s[i] == '_'); } pref[0][0][0] = true; for (int i = 1; i <= n; ++i){ for (int j = 0; j <= k; ++j) { if (s[i] == '.' || s[i] == '_') pref[i][j][0] = pref[i-1][j][0] || pref[i-1][j][1]; if (s[i] == 'X' || s[i] == '.') { if (j == 0) continue; if (i - c[j-1] < 0 || prefw[i] - prefw[i - c[j-1]] > 0 || !pref[i - c[j-1]][j-1][0]) continue; pref[i][j][1] = true; } } } suf[n+1][k+1][0] = true; for (int i = n; i >= 1; --i){ for (int j = k+1; j >= 1; --j) { if (s[i] == '.' || s[i] == '_') suf[i][j][0] = suf[i+1][j][0] || suf[i+1][j][1]; if (s[i] == 'X' || s[i] == '.') { if (j == k+1) continue; if (i + c[j-1] > n+1 || prefw[i + c[j-1] - 1] - prefw[i-1] > 0 || !suf[i + c[j-1]][j+1][0]) continue; suf[i][j][1] = true; } } } vector<bool> posb(n+1), posw(n+1); for (int i = 1; i <= n; ++i){ if (s[i] == 'X') continue; for (int j = 0; j <= k; ++j) { posw[i] = posw[i] || ((pref[i-1][j][1] || pref[i-1][j][0]) && (suf[i+1][j+1][1] || suf[i+1][j+1][0])); } } vector<pair<int, int>> v; for (int j = 1; j <= k; ++j){ for (int i = 1; i <= n; ++i) { if (!pref[i-1][j-1][0] || !suf[i + c[j-1]][j+1][0]) continue; bool flag = true; for (int l = i; l < i + c[j-1]; ++l) { if (s[l] == '_') flag = false; } if (!flag) continue; v.push_back(make_pair(i, i + c[j-1] - 1)); } } int sz = v.size(); vector<pair<int, int>> arr; for (int i = 0; i < sz; ++i){ int l = v[i].first; int r = v[i].second; while (i + 1 < sz && v[i+1].first <= r) r = v[++i].second; arr.push_back({l, r}); } for (auto [l, r] : arr){ for (int i = l; i <= r; ++i) posb[i] = true; } string res; for (int i = 1; i <= n; ++i){ if (posw[i] && posb[i]) res.push_back('?'); else if (posw[i]) res.push_back('_'); else res.push_back('X'); } return res; }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:76:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for (auto [l, r] : arr){
      |               ^
#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...