이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+45;
const int K = 105;
int n,k;
string s;
int c[K];
int pf[N],suf[N];
string prazna(){
int sum = 0;
for(int i = 1; i <= k; i++) sum += c[i];
if(sum == n-(k-1)){
string ans = "";
for(int i = 1; i <= k; i++){
for(int j = 1; j <= c[i]; j++) ans += 'X';
if(i < k) ans += '_';
}
return ans;
}
for(int i = 1; i <= k; i++) pf[i] = pf[i-1]+c[i];
for(int i = k; i >= 1; i--) suf[i] = suf[i+1]+c[i];
string ans = s;
for(int i = 0; i < n; i++){
/// da li moze da bude X na i?
bool mozex = 0;
for(int j = 1; j <= k; j++){
for(int poc = max(0,i-c[j]+1); poc <= i && poc+c[j]-1 < n; poc++){
if(pf[j-1]+(j-1) <= poc && suf[j+1]+(k-(j+1)+1) <= n-poc-1) mozex = 1;
}
}
/// da li moze da bude _ na i?
bool mozey = 0;
if(k == 1) mozey = (i <= n-1-c[1] || i >= c[1]);
for(int j = 1; j < k; j++){
if(pf[j]+(j-1) <= i && suf[j+1]+(k-(j+1)) <= n-i-1) mozey = 1;
}
mozey |= (i <= n-(sum+k-1)-1 || i >= sum+k-1);
if(mozex && mozey) ans[i] = '?';
else if(mozex) ans[i] = 'X';
else if(mozey) ans[i] = '_';
}
return ans;
}
bool pfdp[K][N],sfdp[K][N];
string novo(){
int sum = 0;
for(int i = 1; i <= k; i++) sum += c[i];
if(sum == n-(k-1)){
string ans = "";
for(int i = 1; i <= k; i++){
for(int j = 1; j <= c[i]; j++) ans += 'X';
if(i < k) ans += '_';
}
return ans;
}
for(int i = 1; i <= k; i++) pf[i] = pf[i-1]+c[i];
for(int i = k; i >= 1; i--) suf[i] = suf[i+1]+c[i];
for(int i = 0; i <= n; i++) pfdp[0][i] = 1;
for(int j = 1; j <= k; j++){
for(int i = 1; i <= n; i++){
pfdp[j][i] |= pfdp[j][i-1]; /// stavi _ na i
if(i < c[j]) continue;
bool moze = 1;
for(int h = i-c[j]+1; h <= i; h++){ /// stavi j-ti blok tako da se zavrsava na i
if(s[h-1] == '_') moze = 0;
}
pfdp[j][i] |= (moze && pfdp[j-1][i-c[j]]);
}
}
for(int i = n+1; i >= 1; i--) sfdp[k+1][i] = 1;
for(int j = k; j >= 1; j--){
for(int i = n; i >= 1; i--){
sfdp[j][i] |= sfdp[j][i+1]; /// stavi _ na i
if(n-i+1 < c[j]) continue;
bool moze = 1;
for(int h = i; h <= i+c[j]-1; h++){
if(s[h-1] == '_') moze = 0;
}
sfdp[j][i] |= (moze && sfdp[j+1][i+c[j]]);
}
}
vector <int> bry(n+1,0);
for(int i = 1; i <= n; i++) bry[i] = bry[i-1]+(s[i-1] == '_');
string ans = s;
for(int i = 0; i < n; i++){
if(s[i] == '_'){
ans[i] = '_';
continue;
}
/// da li moze da bude X na i?
bool mozex = 0;
for(int j = 1; j <= k; j++){
for(int poc = max(0,i-c[j]+1); poc <= i && poc+c[j]-1 < n; poc++){
if(bry[poc+c[j]]-bry[poc] == 0 && pfdp[j-1][poc] && sfdp[j+1][poc+c[j]+1]) mozex = 1;
}
}
/// da li moze da bude _ na i?
bool mozey = 0;
if(k == 1) mozey = (i <= n-1-c[1] || i >= c[1]);
for(int j = 1; j < k; j++){
if(pf[j]+(j-1) <= i && suf[j+1]+(k-(j+1)) <= n-i-1) mozey = 1;
}
mozey |= (i <= n-(sum+k-1)-1 || i >= sum+k-1);
if(mozex && mozey) ans[i] = '?';
else if(mozex) ans[i] = 'X';
else if(mozey) ans[i] = '_';
}
return ans;
}
string solve_puzzle(string s1,vector <int> c1){
n = s1.size();
k = c1.size();
s = s1;
for(int i = 1; i <= k; i++) c[i] = c1[i-1];
bool prz = 1,nemax = 1;
for(auto f : s){
if(f != '.') prz = 0;
if(f == 'X') nemax = 0;
}
if(n <= 100 && prz){
return prazna();
}
if(n <= 100 && nemax){
return novo();
}
}
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
150 | }
| ^
# | 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... |