Submission #1211646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211646		cpdreamer	Paint By Numbers (IOI16_paint)	C++20	90 / 100	271 ms	589824 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const long long  INF = 1e12;
typedef long long ll;
const ll MOD=(ll) 998244353;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(),v.end()
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=(int)s.size();
    int k=(int)c.size();
    V<V<bool>>dp(n+1,V<bool>(k+1, false));
    V<int>g;
    g.pb(0);
    for(auto u:c){
        g.pb(u);
    }
    s=';'+s;
    s+=';';
    dp[0][0]=true;
    bool check[n+1][n+1];
    for(int i=1;i<=n;i++){
        if(s[i]!='_'){
            check[i][i]=true;
        }
        else
            check[i][i]=false;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j+i<=n;j++){
            int l=j,r=i+j;
            if(s[r]!='_'){
                check[l][r]=check[l][r-1];
            }
            else
                check[l][r]=false;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(s[i]=='_' || s[i]=='.'){
                dp[i][j]=dp[i-1][j] || dp[i][j];
            }
            if(j==0 || s[i]=='_' || i<g[j])continue;
            bool flag=true;
            for(int a=i;a>i-g[j];a--){
                if(s[a]=='_'){
                    flag=false;
                }
            }
            if(j==1) {
                if (flag) {
                    dp[i][j] = dp[i - g[j]][j - 1] || dp[i][j];
                }
            }
            else{
                if( flag && i-g[j]-1>=0 && (s[i-g[j]]=='_' || s[i-g[j]]=='.')){
                    dp[i][j] = dp[i - g[j]-1][j - 1] || dp[i][j];
                }
            }
        }
    }
    V<V<bool>>dp1(n+2,V<bool>(k+1, false));
    dp1[n+1][k+1]=true;
    for(int i=n;i>=1;i--){
        for(int j=k+1;j>=1;j--){
            if(s[i]=='_' || s[i]=='.'){
                dp1[i][j]=dp1[i+1][j] || dp1[i][j];
            }
            if(j==k+1 || s[i]=='_' || i+g[j]>n+1)continue;
            bool flag=true;
            for(int a=i;a<i+g[j];a++){
                if(s[a]=='_'){
                    flag=false;
                }
            }
            if(j==k) {
                if (flag) {
                    dp1[i][j] = dp1[i + g[j]][j + 1] || dp1[i][j];
                }
            }
            else{
                if( flag && i+g[j]+1<=n+1 && (s[i+g[j]]=='_' || s[i+g[j]]=='.')){
                    dp1[i][j] = dp1[i + g[j]+1][j + 1] || dp1[i][j];
                }
            }
        }
    }
    V<V<bool>>p(n+1,V<bool>(2,false));
    for(int i=1;i<=n;i++){
        if(s[i]=='_'){p[i][0]=true;continue;}
        if(s[i]=='X'){p[i][1]=true;continue;}
        for(int j=0;j<=k;j++){
            if(dp[i-1][j] && dp1[i+1][j+1]){
                p[i][0]=true;
            }
            if(j==0)continue;
            for(int a=1;a<=g[j];a++){
                if(i-a>=0 && i+g[j]-a+1<=n+1){
                    bool flag=check[i-a+1][i+g[j]-a];
                    if(!flag)continue;
                    if(j==1 && k==1){
                        if(dp[i-a][j-1] && dp1[i+g[j]-a+1][j+1]){
                            p[i][1]=true;
                        }
                        continue;
                    }
                    if(j==1){
                        if(i+g[j]-a+2<=n+1 && s[i+g[j]-a+1]!='X'){
                            if(dp[i-a][j-1] && dp1[i+g[j]-a+2][j+1]){
                                p[i][1]=true;
                            }
                        }
                    }
                    else if(j==k){
                        if(i-a-1>=0 && s[i-a]!='X'){
                            if(dp[i-a-1][j-1] && dp1[i+g[j]-a+1][j+1]){
                                p[i][1]=true;
                            }
                        }
                    }
                    else{
                        if(i+g[j]-a+2<=n+1 && s[i+g[j]-a+1]!='X' &&  i-a-1>=0 && s[i-a]!='X'){
                            if(dp[i-a-1][j-1] && dp1[i+g[j]-a+2][j+1]) {
                                p[i][1]=true;
                            }
                        }
                    }
                }
            }
        }
    }
    string ans;
    for(int i=1;i<=n;i++){
        if(p[i][0] && p[i][1])ans+='?';
        else if(p[i][0])ans+='_';
        else ans+='X';
    }
    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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10