제출 #119028

#제출 시각아이디문제언어결과실행 시간메모리
119028turbatPaint By Numbers (IOI16_paint)C++14
0 / 100
62 ms82552 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define N 200005 int n, k, cntw[N], cntb[N], cnt[105], canw[N], canb[N]; vector <int> c; string s, ans; int dp[N][105], paint[N][105]; int solve(int idx, int col){ if (col == -1 && cntb[idx]) return 0; if (col == -1 && !cntb[idx]) return 1; if (idx < 2) return 0; if (dp[idx][col] == -1) return dp[idx][col]; dp[idx][col] = 0; if (s[idx] == '_' || s[idx] == '.') dp[idx][col] = solve(idx - 1, col); if (s[idx] == 'X' || s[idx] == '.') if (idx - c[col] > 0 && cntw[idx] - cntw[idx - c[col]] == 0 && s[idx - c[col]] != 'X') if (solve(idx - c[col] - 1, col - 1)){ dp[idx][col] = 1; paint[idx][col]++; paint[idx - c[col]][col]--; cnt[col]++; } return dp[idx][col]; } // 01234 // __XXX string solve_puzzle(string ss, vector<int> cc) { s = "__" + ss; c = cc; n = s.size(); k = c.size(); for (int i = 1;i < n;i++){ if (s[i] == '_') cntw[i]++; cntw[i] += cntw[i - 1]; if (s[i] == 'X') cntb[i]++; cntb[i] += cntb[i - 1]; } memset(dp, -1, sizeof dp); solve(n - 1, k - 1); for (int i = 0;i < k;i++){ int sum = 0; for (int j = n - 1;j > 1;j--){ sum += paint[j][i]; if (!sum) canw[j]++; if (sum == cnt[i]) canb[j] = 1; } } for (int i = 2;i < n;i++){ if (canb[i]) ans += 'X'; else if (cntw[i] == k) ans += '_'; else ans += '?'; } 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...