Submission #1204905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204905		m5588ohammed	Paint By Numbers (IOI16_paint)	C++20	32 / 100	11 ms	20044 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool dp1[200001][101],dp2[200001][101],vis[200001][101];
int siz[101],pre[200001][2],near1[200001],near2[200001],far1[200001],far2[200001];
array <int,2> interv1[200001],interv2[200001];
int n,k;
string s;
int sum(int l,int r,int u){
    return pre[r][u]-pre[l-1][u];
}
bool dfs1(int i,int gr){
    if(vis[i][gr]!=0) return dp1[i][gr];
    
    if(i==n+1){
        if(gr==k+1) return 1;
        return 0;
    }
    vis[i][gr]=1;
    if(s[i]=='X') return 0;

    if(i<=n){
        dp1[i][gr]|=dfs1(i+1,gr);
    }

    if(i+siz[gr]<=n&&gr!=k+1&&sum(i+1,i+siz[gr],0)==0){
        dp1[i][gr]|=dfs1(i+siz[gr]+1,gr+1);
    }
    return dp1[i][gr];
}
bool dfs2(int i,int gr){
    if(vis[i][gr]!=0) return dp2[i][gr];
    
    if(i==0){
        if(gr==0) return 1;
        return 0;
    }
    vis[i][gr]=1;
    if(s[i]=='X') return 0;

    if(i>=1){
        dp2[i][gr]|=dfs2(i-1,gr);
    }

    if(i-siz[gr]>=0&&gr!=0&&sum(i-siz[gr],i-1,0)==0){
        dp2[i][gr]|=dfs2(i-siz[gr]-1,gr-1);
    }
    return dp2[i][gr];
}
string solve_puzzle(string t, vector<int> c) {
    s="a";s+=t;
    n=s.size()-1;k=c.size();
    for(int i=0;i<c.size();i++) siz[i+1]=c[i];
    for(int i=1;i<=n;i++){
        if(s[i]=='X') pre[i][1]++;
        if(s[i]=='_') pre[i][0]++;
        pre[i][0]+=pre[i-1][0];
        pre[i][1]+=pre[i-1][1];
    }
    near1[0]=far2[0]=0;
    for(int i=1;i<=n+1;i++){
        near1[i]=near1[i-1];
        if(s[i]=='_') near1[i]=i;
        if(s[i]=='X') far2[i]=i;
    }
    near2[n+1]=far1[n+1]=n+1;
    for(int i=n;i>=0;i--){
        near2[i]=near2[i+1];
        far1[i]=far1[i+1];
        if(s[i]=='_') near2[i]=i;
        if(s[i]=='X') far1[i]=i;
    }
    dfs1(siz[1]+1,2);
    dfs1(1,1);

    memset(vis,0,sizeof vis);
    dfs2(n-siz[k],k-1);
    dfs2(n,k);
    dp1[0][1]=1;
    dp2[n+1][k]=1;
    for(int gr=0;gr<=k+1;gr++){
        interv1[gr]={n+1,n+1};
        interv2[gr]={-1,-1};
        for(int i=0;i<=n+1;i++){
            //cout<<"YES "<<i<<" "<<gr<<" "<<dp1[i][gr]<<endl;
            if(dp1[i][gr]==1){
                if(interv1[gr][0]==n+1) interv1[gr][0]=i;
                interv1[gr][1]=i;
            }
            if(dp2[i][gr]==1){
                if(interv2[gr][0]==-1) interv2[gr][0]=i;
                interv2[gr][1]=i;
            }
        }
    }
    interv2[k][1]=n+1;
    if(interv2[k][0]==-1) interv2[k][0]=n+1;
    
    interv1[1][0]=0;
    if(interv1[1][1]==n+1) interv1[1][1]=0;
    //cout<<interv2[1][0]<<" "<<interv2[1][1]<<endl;
    //cout<<dp1[3][1]<<endl;
    string ans="";
    for(int i=1;i<=n;i++){
        bool B=0,W=0;
        for(int gr=1;gr<=k;gr++){
            W|=dp1[i][gr];  
            //if(i==3&&gr==1) cout<<interv2[gr][0]<<" "<<far2[interv2[gr][0]]<<" "<<max(i,far2[interv2[gr][0]])<<" "<<interv1[gr][1]<<endl;
            if(i<=interv1[gr][0]||i>=interv2[gr][1]||(near2[i]-near1[i]-1)<siz[gr]||(max(i,far2[interv2[gr][0]])-min(i,far1[interv1[gr][1]])+1)>siz[gr]) continue;
            int siz1=max(0,(interv2[gr][0]-i))+max(0,(i-interv1[gr][1]));
            int siz2=max(0,(interv2[gr][1]-i))+max(0,(i-interv1[gr][0]));
            //if(i==4) cout<<i<<" "<<gr<<" "<<max(0,(i-interv1[gr][1]))<<" "<<siz2-1<<endl;
            // exit(0);
            if(siz1-1<=siz[gr]&&siz[gr]-1<=siz2) B=1;
        }
        W|=dp1[i][k+1];  
        //cout<<W<<" "<<B<<endl;
        if(W==0&&B==1) ans+='X';
        if(W==1&&B==0) ans+='_';
        if(W==1&&B==1) ans+='?';
    }
    //cout<<n<<endl;
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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