| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 290086 | shayan_p | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "paint.h"
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 110, mod = 1e9 + 7, inf = 1e9 + 10;
bool dp[maxn][maxn], any[maxn][maxn];
bool solve(string &s, vector<int> &c){
for(int i = 1; i <= sz(s); i++){
any[i][i] = s[i-1] == '_';
for(int j = i+1; j <= sz(s); j++){
any[i][j]= any[i][j-1] || s[j-1] == '_';
}
}
dp[0][0] = 1;
for(int i = 0; i <= sz(c); i++){
for(int j = 1; j <= sz(s); j++){
dp[i][j] = 0;
if(s[j-1] != 'X')
dp[i][j]|= dp[i][j-1];
if(i > 0){
if(j > c[i-1])
dp[i][j]|= !any[j-c[i-1]+1][j] && s[j-1-c[i-1]] != 'X' && dp[i-1][j-c[i-1]-1];
if(j == c[i-1])
dp[i][j]|= !any[1][j] && i == 1;
}
}
}
return dp[sz(c)][sz(s)];
}
string solve_puzzle(string s, vector<int> c){
string ans = s;
for(int i = 0; i < sz(s); i++){
if(s[i] == '.'){
s[i] = 'X';
bool A = solve(s, c);
s[i] = '_';
bool B = solve(s, c);
if(A && B)
ans[i] = '?';
else if(A)
ans[i] = 'X';
else if(B)
ans[i] = '_';
else
assert(0);
s[i] = '.';
}
}
return ans;
}