Submission #850614

#	Time	Username	Problem	Language	Result	Execution time	Memory
850614		abcvuitunggio	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1994 ms	174356 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
int n,k,dp[200001][101],dp2[200001][101],res[200001],a[200001],sum[200002],sum2[200002];
string c="._X?";
vector <int> v;
int f(int i, int j){
    if (j<0)
        return (i<0||!sum2[i]);
    if (i<0)
        return 0;
    if (dp[i][j]!=-1)
        return dp[i][j];
    dp[i][j]=(a[i]==2?0:f(i-1,j));
    if (j>=0)
        if (i+1>=v[j])
            if (i-v[j]<0||a[i-v[j]]!=2)
                if (!(sum[i]-(i<v[j]?0:sum[i-v[j]])))
                    dp[i][j]|=f(i-v[j]-1,j-1);
    return dp[i][j];
}
int g(int i, int j){
    if (j>=k)
        return (i>=n||sum2[n-1]==(i?sum2[i-1]:0));
    if (i>=n)
        return 0;
    if (dp2[i][j]!=-1)
        return dp2[i][j];
    dp2[i][j]=(a[i]==2?0:g(i+1,j));
    if (j<k)
        if (n-i>=v[j])
            if (i+v[j]>=n||a[i+v[j]]!=2)
                if (!(sum[i+v[j]-1]-(i?sum[i-1]:0)))
                    dp2[i][j]|=g(i+v[j]+1,j+1);
    return dp2[i][j];
}
string solve_puzzle(string s, vector <int> C){
    n=s.length();
    v=C;
    k=v.size();
    for (int i=0;i<n;i++)
        if (s[i]=='_')
            a[i]=1;
        else if (s[i]=='X')
            a[i]=2;
    sum[0]=(a[0]==1);
    sum2[0]=(a[0]==2);
    for (int i=1;i<n;i++){
        sum[i]=sum[i-1]+(a[i]==1);
        sum2[i]=sum2[i-1]+(a[i]==2);
    }
    memset(dp,-1,sizeof(dp));
    memset(dp2,-1,sizeof(dp2));
    for (int i=0;i<k;i++)
        for (int j=0;j+v[i]<=n;j++)
            if ((!j||a[j-1]!=2)&&(j+v[i]==n||a[j+v[i]]!=2)&&!(sum[j+v[i]-1]-(j?sum[j-1]:0)))
                if (f(j-2,i-1)&&g(j+v[i]+1,i+1)){
                    res[j]+=2;
                    res[j+v[i]]-=2;
                }
    for (int i=1;i<n;i++)
        res[i]+=res[i-1];
    for (int i=0;i<n;i++){
        res[i]=min(res[i],2);
        if (a[i])
            res[i]=a[i];
        else{
            for (int j=0;j<=k;j++)
                if (f(i-1,j-1)&&g(i+1,j)){
                    res[i]|=1;
                    break;
                }
        }
        s[i]=c[res[i]];
    }
    return s;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10