Submission #276012

#	Time	Username	Problem	Language	Result	Execution time	Memory
276012		brcode	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	512 KiB

paint

#include <iostream>
#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int MAXN = 1000;
vector<vector<int>> res;
vector<int> c;

int pref[MAXN];
bool dp[MAXN][250];
int l[250];
int r[250];
bool zero[250];
string solve_puzzle(string s,vector<int> v1){
    int k = v1.size();
    int n = s.length();
    s = '#'+s;
    for(int i=1;i<=n;i++){
        pref[i] = pref[i-1]+(s[i] == '_');
    }
    c.push_back(0);
    for(int x:v1){
        c.push_back(x);
    }
    for(int i=0;i<=n;i++){
        dp[i][0] = true;
    }
    for(int j=1;j<=(int)v1.size();j++){
        for(int i=1;i<=n;i++){
            
            if(j!=1 && i-c[j]-1<0){
                dp[i][j] = false;
                continue;
            }
            
            int lim = i-c[j]-1;
            if(j==1 && lim == -1){
                lim++;
                
            }
            if(pref[i]!=pref[i-c[j]]){
                dp[i][j] = false;
                
                continue;
            }
            for(int ind = lim;ind>=0;ind--){
                
                if(dp[ind][j-1] == true){
                    dp[i][j] = true;
                    break;
                }
            }
        }
    }
    //cout<<dp[1][3]<<endl;
    int m = v1.size();
    for(int i=n;i>=1;i--){
        if(dp[i][m]){
            r[m] = i;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        if(dp[i][m]){
            l[m] = i;
            break;
        }
    }
    
    string res="";
    for(int i=0;i<n;i++){
        res+='?';
    }
    for(int i=l[m];i>=r[m]-c[m]+1;i--){
        res[i-1] = 'X';
    }
    for(int i=n;i>=r[m]+1;i--){
        res[i-1] = '_';
    }
    for(int i=l[m]-c[m]+1;i<=r[m];i++){
        
        bool ok = false;
        
        for(int j=i;j<=min(i+c[m]-1,r[m]);j++){
            ok|=dp[j][m];
        }
        if(ok){
           // cout<<i<<endl;
            zero[i] = true;
            
        }
    }
    //cout<<dp[8][1]<<endl;
    //cout<<l[m]<<" "<<r[m]<<endl;
    for(int i=m-1;i>=1;i--){
        int lim = r[i+1]-c[i+1]-1;
        for(int j=lim;j>=0;j--){
            if(dp[j][i]){
                r[i] = j;
                break;
            }
        }
        for(int j=1;j<=lim;j++){
            if(dp[j][i]){
                l[i] = j;
                break;
            }
        }
        for(int j=l[i];j>=r[i]-c[i]+1;j--){
            res[j-1] = 'X';
            
        }
        for(int j=l[i]-c[i]+1;j<=r[i];j++){
           
            bool ok = false;
            for(int ind = j;ind<=min(j+c[i]-1,r[i]);ind++){
                ok|=dp[ind][i];
            }
            if(ok){
                
                zero[j] = true;
            }
        }
    }
    
    for(int i=1;i<=l[1]-c[1];i++){
        
        res[i-1] = '_';
        
    }
    for(int i=1;i<=n;i++){
        if(!zero[i]){
            
            res[i-1] = '_';
        }
    }
    return res;
}

/*int main(){
    vector<int> tmp;
    tmp.push_back(3);
    cout<<solve_puzzle("..._._....", tmp)<<endl;
}*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:15:9: warning: unused variable 'k' [-Wunused-variable]
   15 |     int k = v1.size();
      |         ^

• 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