제출 #125480

#제출 시각아이디문제언어결과실행 시간메모리
125480streifiPaint By Numbers (IOI16_paint)C++14
59 / 100
2 ms380 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; int N, K; string s; vector<int> c; vector<bool> black, white; vector<int> prefblack, prefwhite; vector<vector<int>> memo; bool dp(int i, int k) { if (i > N+1) return 0; if (memo[i][k] != -1) return memo[i][k]; if (i == N+1) return k == K; bool one = s[i] != 'X' && dp(i+1, k); if (one) white[i] = true; bool two = false; if (k < K && i+c[k]+1 <= N+1) { two = s[i] != 'X' && s[i+c[k]+1] != 'X' && prefwhite[i+c[k]+1] == prefwhite[i+1] && dp(i+c[k]+1, k+1); } if (two) { if (black[i+2]) { black[i+1] = true; white[i] = true; } else { white[i] = white[i+c[k]+1] = true; for (int j = i+1; j <= i+c[k]; ++j) black[j] = true; } } memo[i][k] = one || two; //cout << i << " " << k << " " << one << " " << two << endl; return memo[i][k]; } string solve_puzzle(string _s, vector<int> _c) { s = string("_")+_s, c = _c; N = s.size()-1; K = c.size(); black.assign(N+5, 0), white.assign(N+5, 0); prefblack.assign(N+5, 0), prefwhite.assign(N+5, 0); memo.assign(N+5, vector<int>(K+5, -1)); for (int i = 0; i <= N; ++i) { prefblack[i+1] = prefblack[i]+(s[i]=='X'); //cout << i << endl; //cout << prefwhite[i+1] << endl; //cout << prefwhite[i] << endl; //cout << s[i] << endl; prefwhite[i+1] = prefwhite[i]+(s[i]=='_'); } for (int i = 0; i < 5; ++i) { prefblack.push_back(prefblack.back()); prefwhite.push_back(prefwhite.back()); } string ans; if (!dp(0, 0)) cout << "not good" << endl; for (int i = 1; i <= N; ++i) { if (black[i] && white[i]) ans.push_back('?'); else if (black[i]) ans.push_back('X'); else if (white[i]) ans.push_back('_'); else cout << "shouldn\'t have happened"; } 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...