Submission #598397

#	Time	Username	Problem	Language	Result	Execution time	Memory
598397		chirathnirodha	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2068 ms	219080 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first 
#define S second 
 
bool dp[200000][100];
void createdp(string s,int n,int k,vector<int> c){
    memset(dp,false,sizeof(dp));
    int lb[n],lw[n];
    int cb=-1,cw=-1;
    for(int i=0;i<n;i++){
        lb[i]=cb;lw[i]=cw;
        if(s[i]=='X')cb=i;
        if(s[i]=='_')cw=i;
    }
    vector<int> lastval[k];
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            if(s[i]=='_' || i-c[j]<-1)continue;
 
            if(i-c[j]==-1){
                if(lw[i]<=i-c[j] && j==0){
                    dp[i][j]=true;
                    lastval[j].PB(i);
                }
                continue;
            }
            if(lw[i]>i-c[j])continue;
            int lastbl=lb[i-c[j]+1];
            if(j==0 && lastbl!=-1)continue;
            if(j>0){
                auto low=lower_bound(lastval[j-1].begin(),lastval[j-1].end(),lastbl);
                if(low==lastval[j-1].end() || *low>=i-c[j])continue;
            }
            dp[i][j]=true;
            lastval[j].PB(i);
        }
    }
}
string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    bool pref[n][k],suf[n][k];
 
    string revs=s;reverse(revs.begin(),revs.end());
    vector<int> revc=c;reverse(revc.begin(),revc.end());
 
    createdp(s,n,k,c);
    for(int i=0;i<n;i++)for(int j=0;j<k;j++)pref[i][j]=dp[i][j];
    createdp(revs,n,k,revc);
    for(int i=0;i<n;i++)for(int j=0;j<k;j++)suf[n-1-i][k-1-j]=dp[i][j];
 
    int nearbl[n][2];
    nearbl[0][0]=-1;nearbl[n-1][1]=n;
    int nel[n][k],ner[n][k];
    for(int j=0;j<k;j++)nel[0][j]=-1,ner[n-1][j]=n;
    for(int i=0;i<n-1;i++){
        if(s[i]=='X')nearbl[i+1][0]=i;
        else nearbl[i+1][0]=nearbl[i][0];
        for(int j=0;j<k;j++){
            if(pref[i][j])nel[i+1][j]=i;
            else nel[i+1][j]=nel[i][j];
        }
    }
    for(int i=n-1;i>0;i--){
        if(s[i]=='X')nearbl[i-1][1]=i;
        else nearbl[i-1][1]=nearbl[i][1];
        for(int j=0;j<k;j++){
            if(suf[i][j])ner[i-1][j]=i;
            else ner[i-1][j]=ner[i][j];
        }
    }
    string res=s;
    for(int i=0;i<n;i++){
        if(res[i]=='_' || res[i]=='X')continue;
        for(int j=-1;j<k;j++){
            if(j==-1 && nearbl[i][0]!=-1)continue;
            if(j!=-1 && (nel[i][j]==-1 || nearbl[i][0]>nel[i][j]))continue;
            if(j==k-1 && nearbl[i][1]!=n)continue;
            if(j!=k-1 && (ner[i][j+1]==n || nearbl[i][1]<ner[i][j+1]))continue;
            res[i]='W';
            break;
        }
    }
    for(int j=0;j<k;j++){
      bool proc[n];memset(proc,false,sizeof(proc));
        if(j==k-1){
            for(int i=0;i<n;i++){
                if(nearbl[i][1]!=n || pref[i][j]==false)continue;
                for(int l=0;l<c[j];l++){
                    if(proc[i-l])break;
                    proc[i-l]=true;
                    if(res[i-l]=='.')res[i-l]='X';
                    if(res[i-l]=='W')res[i-l]='?';
                }
            }
            break;
        }
        int cur=0;
        while(cur<n-1){
            if(pref[cur][j]){
                if(ner[cur+1][j+1]==n ||  ner[cur+1][j+1]>nearbl[cur][1]);
                else {
                    for(int i=0;i<c[j];i++){
                        if(proc[cur-i])break;
                        proc[cur-i]=true;
                        if(res[cur-i]=='.')res[cur-i]='X';
                        if(res[cur-i]=='W')res[cur-i]='?';
                    }
                }
            }
            cur++;
        }
    }
    for(int i=0;i<n;i++)if(res[i]=='W')res[i]='_';
    return res;
}

• 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: 0 / 10