Submission #1211811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211811		cpdreamer	Paint By Numbers (IOI16_paint)	C++20	100 / 100	440 ms	58596 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<V<bool>>check(n+1,V<bool>(k+1,false));
    V<int>g;
    g.pb(0);
    for(auto u:c){
        g.pb(u);
    }
    s=';'+s;
    s+=';';
    for(int j=1;j<=k;j++){
        int cnt=0;
        for(int i=1;i<=g[j];i++){
            cnt+=(s[i]=='_');
        }
        check[g[j]][j]=(cnt==0);
        for(int i=g[j]+1;i<=n;i++){
            cnt-=(s[i-g[j]]=='_');
            cnt+=(s[i]=='_');
            check[i][j]=(cnt==0);
        }
    }
    dp[0][0]=true;
    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=check[i][j];
            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=check[i+g[j]-1][j];
            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));
    V<int>b(n+2,0);
    for(int i=1;i<=n;i++){
        if(s[i]=='_'){p[i][0]=true;}
        if(s[i]=='X'){p[i][1]=true;}
        for(int j=0;j<=k;j++){
            if(dp[i-1][j] && dp1[i+1][j+1] && s[i]!='X'){
                p[i][0]=true;
            }
            if(j==0 || (i-g[j])<0)continue;
            if(!check[i][j])continue;
            if(j==1 && k==1){
                if(dp[i-g[j]][j-1] && dp1[i+1][j+1]){
                    b[i-g[j]+1]++;
                    b[i+1]--;
                }
                continue;
            }
            if(j==1){
                if(i+2<=n+1){
                    if(dp[i-g[j]][j-1] && (s[i+1]!='X') && dp1[i+2][j+1]){
                        b[i-g[j]+1]++;
                        b[i+1]--;
                    }
                }
            }
            else if(j==k){
                if(i-g[j]-1>=0){
                    if(dp[i-g[j]-1][j-1] && (s[i-g[j]]!='X') && dp1[i+1][j+1]){
                        b[i-g[j]+1]++;
                        b[i+1]--;
                    }
                }
            }
            else {
                if(i-g[j]-1>=0 && i+2<=n+1){
                    if(dp[i-g[j]-1][j-1] && (s[i-g[j]]!='X') && (s[i+1]!='X') && dp1[i+2][j+1]){
                        b[i-g[j]+1]++;
                        b[i+1]--;
                    }
                }
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=b[i];
        if(s[i]!='.')continue;
        p[i][1]=(cnt>0);
    }
    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: 10 / 10