Submission #1224651

#TimeUsernameProblemLanguageResultExecution timeMemory
1224651LIAPaint By Numbers (IOI16_paint)C++17
59 / 100
3 ms328 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; bool canSolve(const string &s, const vector<int> &c) { int n = s.size(), k = c.size(); vector<vector<char>> dp(n+1, vector<char>(k+1,false)); dp[0][0] = true; for (int i = 1; i <= n; ++i) dp[i][0] = dp[i-1][0] && s[i-1] != 'X'; for (int j = 1; j <= k; ++j) { int len = c[j-1]; for (int i = 1; i <= n; ++i) { if (s[i-1] != 'X' && dp[i-1][j]) dp[i][j] = true; if (!dp[i][j] && i >= len) { bool ok = true; for (int t = i-len; t < i; ++t) if (s[t] == '_') { ok = false; break; } if (ok) { int prev = i - len - 1; if (prev < 0) { if (dp[0][j-1]) dp[i][j] = true; } else if (s[prev] != 'X' && dp[prev][j-1]) { dp[i][j] = true; } } } } } return dp[n][k]; } string solve_puzzle(string s, vector<int> c) { int n = s.size(); string ans(n, '?'); for (int i = 0; i < n; ++i) { if (s[i] == '_') { ans[i] = '_'; continue; } string t = s; t[i] = '_'; if (!canSolve(t, c)) { ans[i] = 'X'; continue; } t[i] = 'X'; if (!canSolve(t, c)) 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...