Submission #889653

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

paint

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
int x[200001];
int y[200001];
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;
    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; 
    }
    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];
            }
        }
    }
    //for(int j=1;j<=m;j++){
    //    for(int i=1;i<=n;i++)
    //        cout<<dp[i][j]<<' ';
    //    cout<<endl;
    //}
    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]){
                p=i-c[j-1]+1;
                q=min(q,i);
            }
        }
        for(int i=p;i<=q;i++)
            s[i]='X';
        for(int i=p+c[j-1];i<=r;i++)
            s[i]='_';
        o=p-2;
        r=q-c[j-1];
    }
    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