| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 363660 | CSQ31 | 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 "grader.cpp"
#include <cstdlib>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
std::string solve_puzzle(std::string s, std::vector<int> c){
int n = sz(s);
int k = sz(c);
int fr = n+2,lt = -1;;
for(int i=n-1;i>=0;i--)if(s[i]=='X')fr = i;
for(int i=0;i<n;i++)if(s[i] == 'X')lt = i;
vector<vector<bool>>dpl(n+2,vector<bool>(k+1,0)),dpr(n+2,vector<bool>(k+1,0)),tl(n+2,vector<bool>(k+1,0)),tr(n+2,vector<bool>(k+1,0));
vector<int>l(k+1,1e9),r(k+1);
for(int i=0;i<n;i++){
if(i){
for(int j=0;j<k;j++){
dpl[i][j]=dpl[i][j]|dpl[i-1][j];
}
}
if(s[i] == '_')continue;
for(int j=0;j<k;j++){
if(!j || (i && dpl[i-1][j-1])){
//we try to extend
bool ok = 1;
for(int e=0;e<c[j];e++){
if(e+i >=n || s[e+i] == '_'){ok = 0;break;}
}
if(i+c[j] < n && s[i+c[j]] == 'X')ok = 0;
if(j == 0 && i>fr)ok = 0;
if(j == k-1 && i+c[j]-1<lt)ok = 0;
if(ok){
//cout<<i<<" "<<j<<" "<<i+c[j]<<s[i+c[j]]<<'\n';
dpl[i+c[j]][j] = 1;
tl[i+c[j]][j] = 1;
}
}
}
}
/*
cout<<"L:"<<'\n';
for(int j=0;j<k;j++){
for(int i=0;i<n;i++)cout<<tl[i][j]<<" ";
cout<<'\n';
}*/
for(int i=n-1;i>=0;i--){
if(i!=n-1){
for(int j=0;j<k;j++){
dpr[i][j] = dpr[i][j]|dpr[i+1][j];
}
}
if(s[i] == '_')continue;
for(int j=k-1;j>=0;j--){
if(j == k-1 || (i!=n-1 && dpr[i+1][j+1])){
//we try to extend
bool ok = 1;
for(int e=0;e<c[j];e++){
if(i-e <0 || s[i-e] == '_'){ok = 0;break;}
}
if(i-c[j] >=0 && s[i-c[j]] == 'X')ok = 0;
if(j == 0 && i>fr)ok = 0;
if(j == k-1 && i+c[j]-1<lt)ok = 0;
if(ok){
if(i-c[j] >=0){
dpr[i-c[j]][j] = 1;
tr[i-c[j]][j] = 1;
}
}
}
}
}
/*
cout<<"R :"<<'\n';
for(int j=0;j<k;j++){
for(int i=0;i<n;i++)cout<<dpr[i][j]<<" ";
cout<<'\n';
}*/
vector<ll>cnt(n+1);
for(int i=0;i<=n;i++){
for(int j=0;j<k;j++){
if(j == k-1 || dpr[i][j+1]){
if(tl[i][j]){
// cout<<i-c[j]<<" "<<i<<'\n';
cnt[i-c[j]]++;
cnt[i]--;
l[j] = min(l[j],i-c[j]);
r[j] = max(r[j],i-1);
}
}
}
}
//for(int i=0;i<k;i++)cout<<l[i]<<" "<<r[i]<<'\n';
string ans(n,'a');
for(int i=0;i<k;i++){
//cout<<r[i]-c[i]+1<<" "<<l[i]+c[i]-1<<'\n';
//cout<<l[i]<<" "<<r[i]<<'\n';
for(int j=max(0,r[i]-c[i]+1);j<l[i]+c[i];j++){
assert(j>=0 && j<n);
ans[j] = 'X';
}
}
for(int i=1;i<n;i++)cnt[i]+=cnt[i-1];
//for(int i=0;i<n;i++)cout<<cnt[i]<<" ";
for(int i=0;i<n;i++){
if(!cnt[i])ans[i] = '_';
else if(ans[i] != 'X')ans[i] = '?';
}
//cout<<ans<<'\n';
// for(int i=0;i<k;i++)cout<<l[i]<<" "<<r[i]<<'\n';
return ans;
}