Submission #889667

#	Time	Username	Problem	Language	Result	Execution time	Memory
889667		Sir_Ahmed_Imran	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	2544 KiB

paint

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
int x[200001];
int y[200001];
int z[200002];
int dp[200001][101];
string solve_puzzle(string s,vector<int> c){
    int n,m,o,p,q,r;
    n=s.size();
    m=c.size();
    s='/'+s;
    z[0]=0;
    for(int i=dp[0][0]=1;i<=n;i++){
        x[i]=x[i-1]+(s[i]=='X');
        y[i]=y[i-1]+(s[i]=='_');
        if(!x[i]) dp[i][0]=1; 
        z[i]=0;
    }
    for(int j=1;j<=m;j++){
        for(int i=c[j-1];i<=n;i++){
            if(j==m && x[n]>x[i]) continue;
            if(s[i]=='X'){
                dp[i][j]=dp[max(i-c[j-1]-1,0)][j-1];
                if(y[i]>y[i-c[j-1]] || s[i-c[j-1]]=='X')
                    dp[i][j]=0;
            }
            else{
                dp[i][j]=dp[max(i-c[j-1]-1,0)][j-1];
                if(dp[i-1][j]) dp[i][j]=1;
                if(y[i]>y[i-c[j-1]] || s[i-c[j-1]]=='X')
                    dp[i][j]=dp[i-1][j];
            }
        }
    }
    o=r=n;
    for(int j=m;j>0;j--){
        p=1;
        q=o;
        for(int i=c[j-1];i<=o;i++){
            if(y[i]==y[i-c[j-1]] && s[i-c[j-1]]!='X'
             && dp[max(i-c[j-1]-1,0)][j-1]){
                z[i-c[j-1]+1]++;
                p=i-c[j-1]+1;
                q=min(q,i);
                z[i+1]--;
            }
        }
        for(int i=p;i<=q;i++)
            s[i]='X';
        o=p-2;
        r=q-c[j-1];
    }
    o=0;
    for(int i=1;i<=n;i++){
        o+=z[i];
        if(o==0) s[i]='_';
    }
    s.erase(s.begin(),s.begin()+1);
    for(int i=0;i<n;i++)
        if(s[i]=='.') s[i]='?';
    return s;
}

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