제출 #119057

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