Submission #637268

#	Time	Username	Problem	Language	Result	Execution time	Memory
637268		ggoh	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1042 ms	113916 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;

int dif[200002][20];
int D[200002][102];
int C[200002];
int sum[200002],csum[200002];
int S[200002];
int n,m;
int f(int p,int q)
{
    int ret1=0,ret2=0,ret=0;
    if(D[p][q])return D[p][q];
    if(p==n)
    {
        if(q==m)ret=1;
        else ret=-1;
        return D[p][q]=ret;
    }
    if(csum[m]-csum[q]>n-p)return D[p][q]=-1;
    if(S[p]==1||S[p]==-1)
    {
        if(q==m || p+C[q]-1>=n || sum[p+C[q]]-sum[p]>0 || S[p+C[q]]==1)ret1=-1;
        else ret1=f(p+C[q]+1,q+1);
        if(ret1==1)
        {
            dif[p][1]++;
            dif[p+C[q]][1]--;
            dif[p+C[q]][0]++;
            dif[p+C[q]+1][0]--;
        }
    }
    if(S[p]==0||S[p]==-1)
    {
        ret2=f(p+1,q);
        if(ret2==1)
        {
            dif[p][0]++;
            dif[p+1][0]--;
        }
    }
    if(ret1==1||ret2==1)ret=1;
    else ret=-1;

    if(S[p]==1)return D[p][q]=ret1;
    else if(S[p]==0)return D[p][q]=ret2;
    else return D[p][q]=ret;
}
string solve_puzzle(string s, vector<int> c) {
    string ans;
    n=s.length()+1;
    for(int i=0;i<n-1;i++)
    {
        if(s[i]=='X')S[i]=1;
        if(s[i]=='.')S[i]=-1;
    }
    for(int i=0;i<n;i++)sum[i+1]=sum[i]+(S[i]==0?1:0);
    m=sz(c);
    for(int i=0;i<m;i++)
    {
        csum[i+1]=csum[i]+c[i];
        C[i]=c[i];
    }
    f(0,0);
    for(int i=1;i<n;i++)
    {
        dif[i][1]+=dif[i-1][1];
        dif[i][0]+=dif[i-1][0];
    }
    for(int i=0;i<n-1;i++)
    {
        if(dif[i][0] && dif[i][1])ans+='?';
        else if(dif[i][0])ans+='_';
        else ans+='X';
    }
    return ans;
}

• 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