| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1066428 | andrei_iorgulescu | Paint By Numbers (IOI16_paint) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}