이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
std::string solve_puzzle(std::string s, std::vector<int> c) {
// dp O(NK)
// nanti transisi coba dari i - 1 terus anggep
// nanti cari semua previous states
// bisa semacam dijkstra semua previous states/bfs
// nanti previous state ada kemungkinan 0 atau 1?
// yg dp[i][k] = 1 nanti jadiin yes terus nanti cari state sebelumnya dmn
// find latest sm find earliest
// nanti cek state boleh transisi kalo???
// dia statenya harus ambil sisanya
int n = s.size(), k = c.size();
bool dp[n + 1][k + 1];
memset(dp, 0, sizeof(dp));
// bisa ambil coba ambil dr n - c[i], i - 1 atau n - 1, i
// nanti case ambilnya bs coba dua"nya
// case valid:
s = " " + s;
c.insert(c.begin(), 0);
int prefa[n + 1], prefb[n + 1];
prefa[0] = prefb[0] = 0;
prefb[0] = 1;
for(int i = 1; i <= n; ++i) {
prefa[i] = prefa[i - 1];
prefb[i] = 0;
if(s[i] == '.')
prefa[i]++, prefb[i]++;
else if(s[i] == 'X')
prefa[i]++;
else
prefb[i]++;
}
for(int i = 0; i <= n; ++i) {
if(s[i] == 'X')
break;
dp[i][0] = 1;
}
for(int j = 1; j <= k; ++j) {
for(int i = 1; i <= n; ++i) {
//cout << i << " " << c[j] << " " << prefa[i] << " " << prefa[i - c[j]] << " " << prefb[i - c[j]] << " " << c[j] << endl;
if(i >= c[j] && prefa[i] - prefa[i - c[j]] == c[j] && prefb[i - c[j]]) {
//cout << "DEBUG " << i << " " << j << endl;
//cout << i - c[j] << " " << j - 1 << endl;
if(i == c[j])
dp[i][j] = dp[i - 1][j] | dp[i - c[j]][j - 1];
else
dp[i][j] = dp[i - 1][j] | dp[i - c[j] - 1][j - 1];
}
else if(s[i] != 'X')
dp[i][j] = dp[i - 1][j];
//cout << dp[i][j] << " ";
}
//cout << endl;
}
// coba dr kemunculan X terakhir atau 0
// terus nanti cek dia bs dateng drmn aja
// cek previousnya yg berlaku
// nanti kalo misal bisa dr i - 1, j berarti sel sekarang itu white
// kalo misal bs dr i - c[j], j - 1 berarti sel sekarang itu black
bool white[n + 1], black[n + 1];
memset(white, 0, sizeof(white));
memset(black, 0, sizeof(black));
bool vis[n + 1][k + 1];
memset(vis, 0, sizeof(vis));
queue<pair<int, int>> q;
vector<pair<int, bool>> bl;
//cout << "TEST" << endl;
for(int i = n; i >= 1; --i) {
if(!dp[i][k])
break;
q.push({i, k});
}
while(q.size()) {
int x = q.front().first, y = q.front().second;
q.pop();
if(vis[x][y] || !dp[x][y] || x < 0 || y < 0)
continue;
vis[x][y] = 1;
if(x != 0 && dp[x - 1][y]) {
//cout << x << " " << y << endl;
white[x] = 1, q.push({x - 1, y});
}
if(y != 0 && x >= c[y] && prefa[x] - prefa[x - c[y]] == c[y] && prefb[x - c[y]] && dp[max(0, x - c[y] - 1)][y - 1]) {
// antara x - c[y] sampai x jadiin black
bl.push_back({x - c[y] + 1, 0}), bl.push_back({x, 1}), q.push({x - c[y] - 1, y - 1});
//cout << x << " " << y << endl;
white[x - c[y]] = 1;
}
}
sort(bl.begin(), bl.end());
int idx = 0, cnt = 0;
for(int i = 1; i <= n; ++i) {
//cout << "TEST" << endl;
while(idx < bl.size() && bl[idx].first == i) {
if(cnt > 0)
black[i] = 1;
if(bl[idx].second)
--cnt;
else
++cnt;
if(cnt > 0)
black[i] = 1;
++idx;
}
//cout << "TEST2" << endl;
if(cnt > 0)
black[i] = 1;
}
string ret = "";
for(int i = 1; i <= n; ++i) {
if(white[i] && black[i])
ret += '?';
else if(white[i])
ret += '_';
else
ret += 'X';
}
return ret;
}
컴파일 시 표준 에러 (stderr) 메시지
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | while(idx < bl.size() && bl[idx].first == i) {
| ~~~~^~~~~~~~~~~
# | 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... |