| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1204410 | notme | Paint By Numbers (IOI16_paint) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "paint.h"
#define pb push_back
using namespace std;
const int maxn = 200005, maxk = 205;
int n, k;
int dp[maxn][maxk], suff[maxn][maxk];
int be1[maxn], be0[maxn];
int pref0[maxn], pref1[maxn];
int get0(int l, int r)
{
if(r < l)return 0;
int rem = 0;
if(l > 0)rem = pref0[l-1];
return pref0[r] - rem;
}
int get1(int l, int r)
{
if(r < l)return 0;
int rem = 0;
if(l > 0)rem = pref1[l-1];
return pref1[r] - rem;
}
int last[maxn], nxt[maxn];
vector < int > p[maxk], g[maxk];
int add[maxn], rem[maxn];
int add0[maxn], rem0[maxn];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
n = s.size();
//cout << n << endl;
k = c.size();
/// pref
if(s[0] == '_')pref0[0] = 1;
else pref0[0] = 0;
for (int i = 1; i < n; ++ i)
{
pref0[i] = pref0[i-1];
if(s[i] == '_')pref0[i] ++;
}
if(s[0] == 'X')pref1[0] = 1;
else pref1[0] = 0;
for (int i = 1; i < n; ++ i)
{
pref1[i] = pref1[i-1];
if(s[i] == 'X')pref1[i] ++;
}
int currlast = -1;
for (int i = 0; i < n; ++ i)
{
if(s[i] == 'X')currlast = i;
last[i] = currlast;
}
int currnxt = n;
for (int i = n-1; i >= 0; -- i)
{
if(s[i] == 'X')currnxt = i;
nxt[i] = currnxt;
}
for (int j = 0; j < k; ++ j)
{
for (int i = 0; i < n; ++ i)
{
if(i < n-1 && s[i+1] == 'X')continue;
int len = c[j];
int endpoint = i - len + 1;
if(endpoint < 0)continue;
int cnt0 = get0(endpoint, i);
if(cnt0)continue;
if(endpoint == 0 && j == 0)
{
dp[i][j] = 1;
continue;
}
else if(endpoint == 0)continue;
if(j == 0)
{
int cnt1 = get1(0, endpoint-1);
if(!cnt1)dp[i][j] = 1;
continue;
}
if(s[endpoint-1] == 'X')continue;
assert(endpoint > 0);
int checkfree = 1;
int arefree = last[endpoint-1];
int lt = 0, rt = p[j-1].size()-1, mid, ans = endpoint;
while(lt <= rt)
{
mid = (lt + rt)/2;
if(p[j-1][mid] >= arefree)
{
ans = p[j-1][mid];
rt = mid - 1;
}
else lt = mid + 1;
}
if(ans <= endpoint - 2)
{
dp[i][j] = 1;
}
}
for (int i = 0; i < n; ++ i)
if(dp[i][j])p[j].push_back(i);
sort(p[j].begin(), p[j].end());
}
for (int j = k-1; j >= 0; -- j)
{
for (int i = n-1; i >= 0; -- i)
{
if(i > 0 && s[i-1] == 'X')
continue;
int len = c[j];
int endpoint = i + len - 1;
if(endpoint > n - 1)continue;
int cnt0 = get0(i, endpoint);
if(cnt0)continue;
if(endpoint == n-1 && j == k-1)
{
suff[i][j] = 1;
continue;
}
else if(endpoint == n-1)continue;
if(j == k-1)
{
int cnt1 = get1(endpoint+1, n-1);
if(!cnt1)suff[i][j] = 1;
continue;
}
int checkfree = 1;
if(s[endpoint+1] == 'X')continue;
int arefree = nxt[endpoint+1];
int lt = 0, rt = g[j+1].size()-1, mid, ans = arefree+1;
while(lt <= rt)
{
mid = (lt + rt)/2;
if(g[j+1][mid] >= endpoint+2)
{
ans = g[j+1][mid];
rt = mid - 1;
}
else lt = mid + 1;
}
if(ans <= arefree)
{
suff[i][j] = 1;
}
}
for (int i = 0; i < n; ++ i)
if(suff[i][j])g[j].push_back(i);
sort(g[j].begin(), g[j].end());
}
for (int j = 0; j < k; ++ j)
{
int len = c[j];
for (int start = 0; start < n; ++ start)
{
int si = start;
int fi = start + len - 1;
if(fi >= n)
{
continue;
}
int cnt0 = get0(si, fi);
if(cnt0)
continue;
int cleanbef = si;
if(si > 0)cleanbef = last[si-1]+1;
int cleanaft = fi;
if(fi < n-1)cleanaft = nxt[fi+1] - 1;
int pre = -1;
for (int i = start - 2; i >= 0; -- i)
{
if(j - 1 >= 0 && dp[i][j-1])pre = i;
if(i < cleanbef)break;
}
if(pre == -1 && j != 0)continue;
if(pre == -1 && j == 0)
{
if(cleanbef == 0)pre = -1;
else continue;
}
int presuff = n;
for (int i = fi + 2; i < n; ++ i)
{
if(j + 1 < n && suff[i][j+1])
presuff = i;
if(i > cleanaft)break;
}
if(presuff == n && j != k-1)
{
continue;
}
if(presuff == n && j == k-1)
{
if(cleanaft == n-1)presuff = n;
else continue;
}
if(si <= fi)
{
add[si] ++;
rem[fi] ++;
}
if(pre+1 <= si-1)
{
add0[pre+1] ++;
rem0[si-1] ++;
}
if(fi+1 <= presuff-1)
{
add0[fi+1] ++;
rem0[presuff-1] ++;
}
/*for (int i = si; i <= fi; ++ i)
be1[i] = 1;
for (int i = pre+1; i <= si-1; ++ i)
be0[i] = 1;
for (int i = fi+1; i <= presuff-1; ++ i)
be0[i] = 1;
*/
}
}
int act = 0;
for (int i = 0; i < n; ++ i)
{
act += add0[i];
be0[i] = act;
act -= rem0[i];
}
act = 0;
for (int i = 0; i < n; ++ i)
{
act += add[i];
be1[i] = act;
act -= rem[i];
}
string ans = "";
for (int i = 0; i < n; ++ i)
{
if(be0[i] && be1[i])ans += "?";
else if(be0[i])ans += "_";
else if(be1[i])ans += "X";
else ans += "?";
}
return ans;
}