This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(ll i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#include "paint.h"
#include <cstdlib>
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
#define ull unsigned long long
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 1e6 + 5, mxq = 2e5 + 5, sq = 400, mxv = 15 * 10, pr = 31;
const int base = (1 << 18);
const ll inf = 2e9, neg = -69420;
void add(int &a, int b){
a += b;
if(a >= mod)a -= mod;
}
int dp[105][105][105];
bool vis[105 * 105 * 105];
vt<int>adj[105 * 105 * 105];
map<pair<pair<int, int>, int>, int>mp;
string s;
int coef(int i, int j, int k){
return(mp[make_pair(make_pair(i, j), k)]);
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
s += '_';
vt<int>a;
forr(i, 0, sz(c)){
a.pb(c[i]);
}
int cnt = 0;
dp[0][0][0] = 1;
for(int i = 0; i <= sz(s); i++){
for(int j = 0; j <= sz(a); j++){
for(int k = 0; k <= a[j]; k++){
mp[{{i, j}, k}] = ++cnt;
}
}
}
for(int i = 0; i < sz(s); i++){
for(int j = 0; j <= sz(a); j++){
for(int k = 0; k <= a[j]; k++){
if(dp[i][j][k] == 0)continue;
if(s[i] == '_' || s[i] == '.'){
if(k == 0){
add(dp[i + 1][j][0], dp[i][j][k]);
adj[coef(i + 1, j, 0)].pb(coef(i, j, k));
}else if(j < sz(a) && k == a[j]){
add(dp[i + 1][j + 1][0], dp[i][j][k]);
adj[coef(i + 1, j + 1, 0)].pb(coef(i, j, k));
}
}if(s[i] == '.' || s[i] == 'X'){
if(j < sz(a) && k < a[j]){
add(dp[i + 1][j][k + 1], dp[i][j][k]);
adj[coef(i + 1, j, k + 1)].pb(coef(i, j, k));
}
}
}
}
}
queue<int>q; q.push(coef(sz(s), sz(a), 0)); vis[coef(sz(s), sz(a), 0)] = 1;
while(!q.empty()){
int nw = q.front(); q.pop();
for(auto i: adj[nw]){
if(!vis[i]){
vis[i] = 1;
q.push(i);
}
}
}
string res = "";
for(int i = 0; i < sz(s) - 1; i++){
bool ok1 = 0, ok2 = 0;
for(int j = 0; j <= sz(a); j++){
for(int k = 0; k <= a[j]; k++){
if(!vis[coef(i, j, k)])continue;
if(k == 0 && vis[coef(i + 1, j, 0)])ok1 = 1;
if(j < sz(a) && a[j] == k && vis[coef(i + 1, j + 1, 0)])ok1 = 1;
if(j < sz(a) && k < a[j] && vis[coef(i + 1, j, k + 1)])ok2 = 1;
}
}
if(ok1 && ok2)res += '?';
else if(ok1)res += '_';
else res += 'X';
}
return(res);
}
# | 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... |