| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1066428 | andrei_iorgulescu | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
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 "paint.h"
#warning That's not FB, that's my FB
using namespace std;
using integer = int;
int modulo = (int)1e9 + 12345;
int n, k;
int a[200005], v[105];
int spb[200005], spw[200005];
int dp[200005][105], ways[200005][105], spdp[200005][105];
int prev_b[200005];
int p[200005];
int f[200005], spf[200005];
string solve_puzzle(string s, vector<integer> c)
{
n = s.size();
k = c.size();
for (int i = 1; i <= k; i++)
v[i] = c[i - 1];
for (int i = 1; i <= n; i++)
{
if (s[i - 1] == 'X')
a[i] = 0;
else if (s[i - 1] == '_')
a[i] = 1;
else
a[i] = 2;
}
prev_b[0] = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == 0)
prev_b[i] = i;
else
prev_b[i] = prev_b[i - 1];
}
for (int i = 1; i <= n; i++)
{
spb[i] = spb[i - 1];
spw[i] = spw[i - 1];
if (a[i] == 0)
spb[i]++;
else if (a[i] == 1)
spw[i]++;
}
ways[n + 2][k + 1] = 1;
ways[n + 1][k + 1] = 1;
for (int i = n; i >= 1; i--)
{
if (a[i] != 0)
ways[i][k + 1] = ways[i + 1][k + 1];
for (int j = 1; j <= k; j++)
{
if (a[i] == 1)
ways[i][j] = ways[i + 1][j];
else if (a[i] == 0)
{
if (i + v[j] - 1 <= n and spw[i + v[j] - 1] == spw[i - 1])
{
if (i + v[j] == n + 1 or a[i + v[j]] != 0)
ways[i][j] = ways[i + v[j] + 1][j + 1];
}
}
else
{
if (i + v[j] - 1 <= n and spw[i + v[j] - 1] == spw[i - 1])
{
//cout << i << ' ' << j << endl;
if (i + v[j] == n + 1 or a[i + v[j]] != 0)
ways[i][j] = ways[i + v[j] + 1][j + 1];
}
if (a[i] != 0)
ways[i][j] += ways[i + 1][j];
if (ways[i][j] >= modulo)
ways[i][j] -= modulo;
}
//cout << i << ' ' << j << ' ' << ways[i][j] << endl;
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
if (i - v[j] + 1 >= 1 and spw[i] == spw[i - v[j]] and (i == n or a[i + 1] != 0))
{
if (j == 1 and spb[i - v[j]] == 0)
dp[i][j] = 1;
else if (j != 1)
{
int x = prev_b[i - v[j]];
if (x == 0)
dp[i][j] = spdp[max(0ll,i - v[j] - 1)][j - 1];
else
dp[i][j] = (spdp[i - v[j] - 1][j - 1] + modulo - spdp[x - 1][j - 1]) % modulo;
}
}
spdp[i][j] = (spdp[i - 1][j] + dp[i][j]) % modulo;
}
}
int nrw = 0;
for (int j = 1; j <= k; j++)
{
for (int i = 1; i <= n; i++)
{
f[i] = (__int128)dp[i][j] * ways[i + 2][j + 1] % modulo;
spf[i] = (spf[i - 1] + f[i]) % modulo;
}
if (j == 1)
nrw = spf[n];
for (int i = 1; i <= n; i++)
{
int inc = (spf[min(n,i + v[j] - 1)] - spf[i - 1] + modulo) % modulo;
p[i] = (p[i] + inc) % modulo;
}
}
string ans;
for (int i = 1; i <= n; i++)
{
if (p[i] == 0)
ans.push_back('_');
else if (p[i] == nrw)
ans.push_back('X');
else
ans.push_back('?');
}
return ans;
}