Submission #713473

#TimeUsernameProblemLanguageResultExecution timeMemory
713473boris_mihovPaint By Numbers (IOI16_paint)C++17
100 / 100
1329 ms99904 KiB
#include "paint.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 200000 + 10; const int MAXK = 100 + 10; const int INF = 1e9; int n, k; std::string s; int lens[MAXK]; bool dp[MAXN][MAXK]; bool bl[MAXN][MAXK]; bool dp2[MAXN][MAXK]; bool bl2[MAXN][MAXK]; int max[MAXN]; int can2[MAXN]; int can[MAXN]; bool f(int pos, int curr) { if (pos >= n) { return (curr == k); } if (bl[pos][curr]) { return dp[pos][curr]; } bl[pos][curr] = true; dp[pos][curr] = false; if (s[pos] != '_' && curr < k && can[pos] >= lens[curr] && (pos + lens[curr] == n || s[pos + lens[curr]] != 'X')) { dp[pos][curr] |= f(pos + lens[curr] + 1, curr + 1); } if (s[pos] != 'X') { dp[pos][curr] |= f(pos + 1, curr); } return dp[pos][curr]; } bool hasX[MAXN]; bool f2(int pos, int curr) { if (pos < 0) { return (curr == -1); } if (curr == -1) { return !hasX[pos]; } if (bl2[pos][curr]) { return dp2[pos][curr]; } bl2[pos][curr] = true; dp2[pos][curr] = false; if (s[pos] != '_' && curr < k && can2[pos] >= lens[curr] && (pos - lens[curr] == -1 || s[pos - lens[curr]] != 'X')) { dp2[pos][curr] |= f2(pos - lens[curr] - 1, curr - 1); } if (s[pos] != 'X') { dp2[pos][curr] |= f2(pos - 1, curr); } return dp2[pos][curr]; } bool canBeBlack[MAXN]; bool canBeWhite[MAXN]; std::string solve_puzzle(std::string S, std::vector <int> c) { s = S; n = s.size(); k = c.size(); for (int i = 0 ; i < k ; ++i) { lens[i] = c[i]; } for (int i = 0 ; i < n ; ++i) { hasX[i] = ((i != 0 && hasX[i - 1]) || s[i] == 'X'); if (s[i] == '_') can2[i] = 0; else if (i == 0) can2[i] = 1; else can2[i] = can2[i - 1] + 1; } for (int i = n - 1 ; i >= 0 ; --i) { if (s[i] == '_') can[i] = 0; else can[i] = can[i + 1] + 1; } for (int i = 0 ; i < n ; ++i) { if (s[i] == 'X') continue; for (int j = 0 ; j <= k ; ++j) { if (f2(i - 1, j - 1) && f(i + 1, j)) { canBeWhite[i] = true; } } } for (int i = 0 ; i < n ; ++i) { if (s[i] == '_' || (i > 0 && s[i - 1] == 'X')) continue; for (int j = 0 ; j < k ; ++j) { if (f2(i - 2, j - 1) && can[i] >= lens[j] && i + lens[j] <= n && (i + lens[j] == n || s[i + lens[j]] != 'X') && f(i + lens[j] + 1, j + 1)) { max[i] = std::max(max[i], lens[j]); } } } int left = 0; for (int i = 0 ; i < n ; ++i) { left = std::max(left - 1, max[i]); if (left > 0) canBeBlack[i] = true; } std::string ans; ans.resize(n); for (int i = 0 ; i < n ; ++i) { if (canBeBlack[i] && canBeWhite[i]) ans[i] = '?'; else if (canBeBlack[i]) ans[i] = 'X'; else if (canBeWhite[i]) ans[i] = '_'; else assert(false); } return ans; }
#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...