Submission #1269831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269831		kl0989e	Paint By Numbers (IOI16_paint)	C++20	100 / 100	294 ms	173996 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

string solve_puzzle(string s, vi c) {
    int n=s.size();
    int k=c.size();
    for (int i=0; i<n; i++) {
        if (s[i]=='.') {
            s[i]='?';
        }
    }
    vector<vi> dp(n+1,vi(k+1,0));
    vi cnt(n+1,0);
    for (int i=0; i<n; i++) {
        cnt[i+1]=cnt[i]+(s[i]=='_');
    }
    dp[0][0]=1;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=k; j++) {
            if (s[i-1]!='X') {
                dp[i][j]|=dp[i-1][j];
            }
            if (j>0 && c[j-1]<=i && cnt[i]-cnt[i-c[j-1]]==0 && (i-c[j-1]-1<0 || s[i-c[j-1]-1]!='X')) {
                dp[i][j]|=(dp[max(i-c[j-1]-1,0)][j-1]);
            }
        }
    }
    reverse(all(s));
    reverse(all(c));
    for (int i=0; i<n; i++) {
        cnt[i+1]=cnt[i]+(s[i]=='_');
    }
    vector<vi> dp1(n+1,vi(k+1,0));
    dp1[0][0]=1;
    for (int i=1; i<=n; i++) {
        for (int j=0; j<=k; j++) {
            if (s[i-1]!='X') {
                dp1[i][j]|=dp1[i-1][j];
            }
            if (j>0 && c[j-1]<=i && cnt[i]-cnt[i-c[j-1]]==0 && (i-c[j-1]-1<0 || s[i-c[j-1]-1]!='X')) {
                dp1[i][j]|=(dp1[max(i-c[j-1]-1,0)][j-1]);
            }
        }
    }
    reverse(all(s));
    reverse(all(c));
    for (int i=0; i<n; i++) {
        cnt[i+1]=cnt[i]+(s[i]=='_');
    }
    int mx=-1;
    for (int i=0; i<n; i++) {
        for (int j=0; j<k; j++) {
            if (s[i]!='_' && i+c[j]<=n && cnt[i+c[j]]-cnt[i]==0) {
                if ((i==0 && j==0) || (i!=0 && s[i-1]!='X' && dp[i-1][j])) {
                    if ((i+c[j]==n && j==k-1) || (i+c[j]!=n && s[i+c[j]]!='X' && dp1[n-i-c[j]-1][k-j-1])) {
                        mx=max(mx,i+c[j]-1);
                    }
                }
            }
        }
        if (s[i]!='?') {
            continue;
        }
        bool a=0,b=0;
        for (int j=0; j<=k; j++) {
            a|=dp[i][j]&dp1[n-i-1][k-j];
        }
        b=i<=mx;
        if (a && b) {
            s[i]='?';
        }
        else if (a) {
            s[i]='_';
        }
        else if (b) {
            s[i]='X';
        }
    }
    return s;
}

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