# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1021851 | vjudge1 | Paint By Numbers (IOI16_paint) | C++17 | 7 ms | 7004 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ent '\n'
typedef long long ll;
using namespace std;
const int maxn = 2e5+12;
int suff[maxn][103];
int pref[maxn][103];
int can[maxn];
int prefw[maxn];
int prefb[maxn];
int c[maxn];
int n, k;
string solve_puzzle(string s, vector<int> C){
n = s.size(), k = C.size();
for(int i=0;i<n;i++){
prefw[i+1] = prefw[i] + (s[i] == '_');
prefb[i+1] = prefb[i] + (s[i] == 'X');
c[i+1] = C[i];
}
string ans = "";
pref[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(s[i-1] != 'X') pref[i][j] = pref[i-1][j];
if(j > 1 && i > c[j] && pref[i-c[j]-1][j-1] && prefw[i] == prefw[i-c[j]] && s[i - c[j] - 1] != 'X') {
pref[i][j] = 1;
}
if(j == 1 && i >= c[j] && pref[i-c[j]][j-1] && prefw[i] == prefw[i-c[j]]){
pref[i][j] = 1;
}
}
}
suff[n+1][k+1] = 1;
for(int i=n;i;i--){
for(int j=k+1;j>0;j--){
if(s[i-1] != 'X') suff[i][j] = suff[i+1][j];
if(j < k && n - i + 1 > c[j] && suff[i+c[j]+1][j+1] && prefw[i+c[j]-1] == prefw[i-1] && s[i + c[j] - 1] != 'X'){
suff[i][j] = 1;
}
if(j == k && n - i + 1 >= c[j] && suff[i+c[j]][j+1] && prefw[i+c[j]-1] == prefw[i-1]){
suff[i][j] = 1;
}
}
}
for(int j=1;j<=k;j++){
for(int l=1;l+c[j]-1<=n;l++){
int r = l + c[j] - 1;
if(prefw[r] - prefw[l-1] == 0 && r + (j != k) <= n && l - 1 - (j != 1) >= 0 &&
pref[l - 1 - (j != 1)][j-1] && suff[r + 1 + (j != k)][j+1] &&
(l == 1 || l > 1 && s[l-2] != 'X') && (r == n || r < n && s[r] != 'X'))
{
can[l]++, can[r+1]--;
}
}
}
for(int i=1;i<=n;i++){
can[i] += can[i-1];
bool ok = 0, fg = 0;
for(int j=0;j<=k;j++){
if(pref[i-1][j] && suff[i+1][j+1] && s[i-1] != 'X'){
fg = 1;
}
}
if(!fg){
ans += 'X';
}
else if(!can[i]){
ans += '_';
}
else{
ans += '?';
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |