Submission #1268182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268182		kl0989e	Paint By Numbers (IOI16_paint)	C++20	80 / 100	2090 ms	704 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()

bool try_solve(string s, vi c) {
    int n=s.size();
    int k=c.size();
    vector<vi> dp(n+2,vi(k+1,0));
    dp[0][0]=1;
    for (int i=0; i<n; i++) {
        for (int j=0; j<=k; j++) {
            if (!dp[i][j]) {
                continue;
            }
            if (s[i]!='X') {
                dp[i+1][j]=1;
            }
            if (i+c[j]>n || j==k) {
                continue;
            }
            bool ok=1;
            for (int l=0; l<c[j]; l++) {
                ok&=s[i+l]!='_';
            }
            ok&=(i+c[j]==n || s[i+c[j]]!='X');
            if (ok) {
                dp[i+c[j]+1][j+1]=1;
            }
        }
    }
    return dp[n][k] || dp[n+1][k];
}

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]='?';
        }
    }
    for (int i=0; i<n; i++) {
        if (s[i]!='?') {
            continue;
        }
        s[i]='_';
        bool a=try_solve(s,c);
        s[i]='X';
        bool b=try_solve(s,c);
        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: 0 / 10
• Subtask 7: 0 / 10