제출 #143006

#제출 시각아이디문제언어결과실행 시간메모리
143006SpeedOfMagicPaint By Numbers (IOI16_paint)C++17
59 / 100
3 ms504 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; //22 6 string solve_puzzle(string s, vector<int> c) { int k = c.size(), n = s.size(); //dp[i][j] - if it's possible to cover all first i characters by using j segments int dp[n][k]; memset(dp, 0, sizeof dp); int blackPref[n], whitePref[n]; for (int i = 0; i < n; i++) { whitePref[i] = (i ? whitePref[i - 1] : 0) + (s[i] == '_'); blackPref[i] = (i ? blackPref[i - 1] : 0) + (s[i] == 'X'); } int prefDP[n][k]; memset(prefDP, 0, sizeof prefDP); for (int i = 0; i < n; i++) { if (i + 1 >= c[0]) { if (i < c[0]) dp[i][0] = whitePref[i] == 0; else dp[i][0] = (whitePref[i] - whitePref[i - c[0]] == 0) && (blackPref[i - c[0]] == 0); } for (int j = 1; j < k; j++) if (i > c[j]) dp[i][j] = (whitePref[i] - whitePref[i - c[j]] == 0) && (s[i - c[j]] != 'X') && prefDP[i - c[j] - 1][j - 1]; dp[i][k - 1] &= blackPref[n - 1] - blackPref[i] == 0; for (int j = 0; j < k; j++) prefDP[i][j] = (i ? prefDP[i - 1][j] : 0) + dp[i][j]; } //for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) cout << dp[j][i]; cout << endl; } for (int i = k - 1; i > 0; i--) for (int j = n - 1; j >= 0; j--) { if (dp[j][i]) { for (int l = j - c[i]; l < n; l++) dp[l][i - 1] = 0; break; } } //for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) cout << dp[j][i]; cout << endl; } int nearest[k]; for (int j = 0; j < k; j++) for (int i = 0; i < n; i++) if (dp[i][j]) { nearest[j] = i; break; } string ans = s; for (char& i : ans) if (i == '.') i = '?'; int canBeBlack[n], canBeWhite[n]; memset(canBeBlack, 0, sizeof canBeBlack); memset(canBeWhite, 0, sizeof canBeWhite); for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) if (dp[i][j]) { canBeBlack[i - c[j] + 1]++; if (i + 1 < n) canBeBlack[i + 1]--; if (j == 0) { canBeWhite[0]++; if (i - c[j] + 1 < n) canBeWhite[i - c[j] + 1]--; } if (j == k - 1) { if (i + 1 < n) canBeWhite[i + 1]++; } if (j > 0 && i - c[j] >= 0) { canBeWhite[nearest[j - 1] + 1]++; if (i - c[j] + 1 < n) canBeWhite[i - c[j] + 1]--; } } int sum = 0, sumw = 0; for (int i = 0; i < n; i++) { sum += canBeBlack[i]; sumw += canBeWhite[i]; //cout << i << " " << sum << " " << sumw << endl; if (sum && sumw) assert(ans[i] == '?'); else if (sum) { assert(ans[i] != '_'); ans[i] = 'X'; } else if (sumw) { assert(ans[i] != 'X'); ans[i] = '_'; } else assert(0); } return ans; } /* ?X?__XX__ ...__.._. 2 2 2 *//* _X_ .X. 1 1 */
#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...