| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482232 | Lobo | Paint By Numbers (IOI16_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 220000
ii n, k, a[maxn], b[maxn], dp1[maxn][110][2], dp2[maxn][110][2];
ii ansb[maxn], answ[maxn], ps[maxn], qtdw[maxn];
string ans;
//0->.
//1->_
//2->X
ii sol1(ii i, ii j, ii ant) {
if(i == 0 && j == 0) return 1;
if(dp1[i][j][ant] != -1) return dp1[i][j][ant];
ii ans = 0;
//if can be white:
if(i != 0 && a[i] != 2) ans = max(ans, sol1(i-1,j,0));
//if can be black:
if(j != 0 && ant == 0 && i-b[j]+1 >= 1 && qtdw[i] - qtdw[i-b[j]] == 0) ans = max(ans, sol1(i-b[j],j-1,1));
return dp1[i][j][ant] = ans;
}
ii sol2(ii i, ii j, ii ant) {
if(i == n+1 && j == k+1) return 1;
if(dp2[i][j][ant] != -1) return dp2[i][j][ant];
ii ans = 0;
//if can be white:
if(i != n+1 && a[i] != 2) ans = max(ans, sol2(i+1,j,0));
//if can be black:
if(j != k+1 && ant == 0 && i+b[j]-1 <= n && qtdw[i+b[j]-1] - qtdw[i-1] == 0) ans = max(ans, sol2(i+b[j],j+1,1));
return dp2[i][j][ant] = ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
string s;
cin >> s >> k;
vector<int> c;
for(ii i = 0; i < k; i++) {
ii x; cin >> x;
c.pb(x);
}
//begin
n = s.size();
k = c.size();
for(ii i = 1; i <= n; i++) {
qtdw[i] = qtdw[i-1];
if(s[i-1] == '.') a[i] = 0;
else if(s[i-1] == '_') {
qtdw[i]++;
a[i] = 1;
}
else a[i] = 2;
}
for(ii i = 1; i <= k; i++) {
b[i] = c[i-1];
}
for(ii i = 0; i <= n+1; i++) {
for(ii j = 0; j <= k+1; j++) {
for(ii ant = 0; ant <= 1; ant++)
dp1[i][j][ant] = dp2[i][j][ant] = -1;
}
}
for(ii i = 1; i <= n; i++) {
for(ii j = 1; j <= k+1; j++) {
//i is white
if(a[i] != 2) answ[i] = max(answ[i], (sol1(i-1,j-1,0)&sol2(i+1,j,0)) );
}
for(ii j = 1; j <= k; j++) {
//interval (i,i+b[j]-1) black
if((sol1(i-1,j-1,1)&sol2(i+b[j],j+1,1)) == 1 && qtdw[i+b[j]-1]-qtdw[i-1] == 0) {
ps[i]++;
ps[i+b[j]]--;
}
}
}
for(ii i = 1; i <= n; i++) {
ps[i]+= ps[i-1];
if(ps[i] >= 1) ansb[i] = 1;
if(answ[i] == 1 && ansb[i] == 1)
ans+= '?';
else if(answ[i] == 1)
ans+= '_';
else if(ansb[i] == 1)
ans+= 'X';
else
cout << "erro";
}
cout << ans << endl;
}