Submission #1059242

#TimeUsernameProblemLanguageResultExecution timeMemory
1059242TAhmed33Paint By Numbers (IOI16_paint)C++98
59 / 100
1 ms348 KiB
#include "paint.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; string solve_puzzle (string s, vector <int> c) { int n = s.length(), k = c.size(); c.insert(c.begin(), 0); c.push_back(0); vector <vector <int>> p(2, vector <int> (n + 4, 0)); vector <vector <int>> h(2, vector <int> (n + 4, 0)); vector <vector <int>> f(k + 2, vector <int> (n + 4, 0)); vector <vector <int>> g(k + 2, vector <int> (n + 4, 0)); vector <vector <int>> good(k + 2, vector <int> (n + 4, 0)); for (int i = 0; i < n; i++) { if (s[i] == '_') p[0][i + 1]++; if (s[i] == 'X') p[1][i + 1]++; } for (int i = 1; i <= n + 1; i++) { p[0][i] += p[0][i - 1]; p[1][i] += p[1][i - 1]; } f[0][0] = 1; for (int i = 1; i <= k; i++) { for (int j = 1; j <= n + 1; j++) { f[i - 1][j] += f[i - 1][j - 1]; } for (int j = c[i]; j <= n; j++) { if (p[0][j] - p[0][j - c[i]] != 0) { continue; } if (j - c[i] == 0) { f[i][j] |= f[i - 1][0] != 0; continue; } int L = 1, R = j - c[i], ans = -1; while (L <= R) { int mid = (L + R) / 2; if (p[1][j - c[i]] - p[1][mid - 1] == 0) { R = mid - 1; ans = mid; } else { L = mid + 1; } } if (ans == -1) { continue; } f[i][j] = (f[i - 1][j - c[i] - 1] - (ans <= 1 ? 0 : f[i - 1][ans - 2])) != 0; } } for (int j = 1; j <= n + 1; j++) { f[k][j] += f[k][j - 1]; } g[k + 1][n + 1] = 1; for (int i = k; i >= 1; i--) { for (int j = n; j >= 1; j--) { g[i + 1][j] += g[i + 1][j + 1]; } for (int j = n - c[i] + 1; j >= 1; j--) { if (p[0][j + c[i] - 1] - p[0][j - 1] != 0) { continue; } if (j + c[i] == n + 1) { g[i][j] |= g[i + 1][n + 1]; continue; } int L = j + c[i], R = n, ans = -1; while (L <= R) { int mid = (L + R) / 2; if (p[1][mid] - p[1][j + c[i] - 1] == 0) { L = mid + 1; ans = mid; } else { R = mid - 1; } } if (ans == -1) { continue; } g[i][j] = (g[i + 1][j + c[i] + 1] - (ans >= n ? 0 : g[i + 1][ans + 2])) != 0; } } for (int i = n; i >= 1; i--) { g[1][i] += g[1][i + 1]; } for (int l = 0; l <= k; l++) { for (int i = 0; i <= n; i++) { if (!f[l][i] - (i == 0 ? 0 : f[l][i - 1])) { continue; } int L = i + 2, R = n + 1, ans = -1; while (L <= R) { int mid = (L + R) / 2; if (p[1][mid - 1] - p[1][i] == 0) { L = mid + 1; ans = mid; } else { R = mid - 1; } } if (ans == -1) { continue; } L = i + 2, R = ans; int ans2 = -1; while (L <= R) { int mid = (L + R) / 2; if (g[l + 1][mid] - g[l + 1][ans + 1]) { L = mid + 1; ans2 = mid; } else { R = mid - 1; } } if (ans2 == -1) { continue; } L = i + 2, R = ans2; int ans3 = -1; while (L <= R) { int mid = (L + R) / 2; if (g[l + 1][i + 2] - g[l + 1][mid + 1]) { R = mid - 1; ans3 = mid; } else { L = mid + 1; } } h[0][i + 1]++; h[0][ans2]--; h[1][i - c[l] + 1]++; h[1][i + 1]--; good[l + 1][ans3]++; good[l + 1][ans2 + 1]--; for (int j = ans3; j <= ans2; j++) { if (g[l + 1][j] - g[l + 1][j + 1]) { h[1][j]++; h[1][j + c[l + 1]]--; } } } } for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) { good[i][j] += good[i][j - 1]; if (good[i][j]) { if (g[i][j] - g[i][j + 1]) { h[1][j]++; h[1][j + c[i]]--; } } } } for (int i = 1; i <= n + 1; i++) { h[0][i] += h[0][i - 1]; h[1][i] += h[1][i - 1]; } string ans; for (int i = 1; i <= n; i++) { if (h[0][i] && h[1][i]) { ans.push_back('?'); } else if (h[0][i]) { ans.push_back('_'); } else { ans.push_back('X'); } } 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...