제출 #200897

#제출 시각아이디문제언어결과실행 시간메모리
200897oofsaucePaint By Numbers (IOI16_paint)C++14
0 / 100
5 ms256 KiB
#include "paint.h" #include <cstdlib> #include <bits/stdc++.h> using namespace std; string s; vector<int> c; int n; int k; vector<bool> defB; vector<bool> mayB; vector<bool> defW; vector<bool> mayW; vector<int> whiteCnt; vector<vector<bool>> visited; vector<vector<bool>> valid; bool solve(int clueIdx, int strIdx) { if(strIdx >= n) return clueIdx == k; if(clueIdx == k) { for(int i = strIdx; i < n; i++) if(s[i] == 'X') return false; for(int i = strIdx; i < n; i++) mayW[i] = true; return true; } if(visited[clueIdx][strIdx]) return valid[clueIdx][strIdx]; visited[clueIdx][strIdx] = true; bool dontpick = s[strIdx] != 'X' && solve(clueIdx, strIdx + 1); // cout << dontpick << endl; if(dontpick) mayW[strIdx] = true; // for(int i = 0; i < c[clueIdx]; i++) { // if(strIdx+i >= n || s[strIdx+i] == '_') return valid[clueIdx][strIdx] = dontpick; // } if(strIdx >= n || (whiteCnt[strIdx] != whiteCnt[strIdx+c[clueIdx]-1])) return valid[clueIdx][strIdx] = dontpick; if(strIdx+c[clueIdx] < n && s[strIdx+c[clueIdx]] == 'X') return valid[clueIdx][strIdx] = dontpick; bool pick = solve(clueIdx + 1, strIdx+c[clueIdx]+1); // cout << pick << endl<<endl; if(pick) { for(int i = 0; i < c[clueIdx]; i++) mayB[strIdx + i] = true; if(strIdx+c[clueIdx] < n) mayW[strIdx+c[clueIdx]] = true; } return valid[clueIdx][strIdx] = pick || dontpick; } string solve_puzzle(string s_, vector<int> c_) { s = s_; c = c_; n = s.size(); k = c.size(); defB.resize(n, false); mayB.resize(n, false); defW.resize(n, false); mayW.resize(n, false); visited.resize(k, vector<bool>(n)); valid.resize(k, vector<bool>(n)); whiteCnt.resize(n, 0); whiteCnt[0] = s[0] == '_'; for(int i = 1; i < n; i++) { whiteCnt[i] = whiteCnt[i-1] + (s[i] == '_'); // cout << whiteCnt[i] << " "; } // cout << endl; string ans = ""; solve(0,0); // for(int i = 0; i < n; i++) cout << mayB[i] << " "; cout << endl; // for(int i = 0; i < n; i++) cout << mayW[i] << " "; cout << endl; for(int i = 0; i < n; i++) { if (mayB[i] && mayW[i]) ans += "?"; else if(mayB[i] && !mayW[i]) ans += "X"; else if(!mayB[i] && mayW[i]) ans += "_"; else if(!mayB[i] && !mayW[i]) 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...