Submission #436387

#	Time	Username	Problem	Language	Result	Execution time	Memory
436387		qwerasdfzxcl	Paint By Numbers (IOI16_paint)	C++14	100 / 100	970 ms	41656 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

bool dpl[200200][101], dpr[200200][101];
int S[200200], N, K;

string solve_puzzle(string str, vector<int> a) {
    string ans;
    N = str.size(), K = a.size();
    ans.resize(str.size());
    str.insert(str.begin(), 0);
    str.push_back(0);
    a.insert(a.begin(), 0);
    for (int i=1;i<=N;i++) S[i] = S[i-1] + (str[i]=='_');
    for (int i=0;i<=N;i++){
        if (str[i]=='X') break;
        dpl[i][0] = 1;
    }
    for (int i=N+1;i;i--){
        if (str[i]=='X') break;
        dpr[i][K+1] = 1;
    }

    for (int j=1;j<=K;j++){
        for (int i=1;i<=N;i++){
            if (i<a[j]) continue;
            if (S[i]-S[i-a[j]]==0){
                bool tmp = (j==1);
                if (i-a[j]-1>=0) tmp = dpl[i-a[j]-1][j-1];
                if (str[i+1]!='X' && str[i-a[j]]!='X') dpl[i][j] |= tmp;
            }
            if (str[i]!='X') dpl[i][j] |= dpl[i-1][j];
        }
    }
    for (int j=K;j;j--){
        for (int i=N;i;i--){
            if (N+1-i<a[j]) continue;
            if (S[i+a[j]-1]-S[i-1]==0){
                bool tmp = (j==K);
                if (i+a[j]+1<=N+1) tmp = dpr[i+a[j]+1][j+1];
                if (str[i+a[j]]!='X' && str[i-1]!='X') dpr[i][j] |= tmp;
            }
            if (str[i]!='X') dpr[i][j] |= dpr[i+1][j];
        }
    }

    /*for (int j=0;j<=K+1;j++){
        for (int i=0;i<=N+1;i++) printf("%d", dpl[i][j]);
        printf("\n");
    }
    printf("\n");
    for (int j=0;j<=K+1;j++){
        for (int i=0;i<=N+1;i++) printf("%d", dpr[i][j]);
        printf("\n");
    }*/
    for (int j=1;j<=K;j++){
        int prv = -1e9;
        for (int i=1;i<=N;i++){
            if (i+a[j]>N+1) break;
            if (S[i+a[j]-1]-S[i-1]==0){
                if (str[i+a[j]]!='X' && str[i-1]!='X'){
                    bool tmp1 = (j==1), tmp2 = (j==K);
                    if (i-2>=0) tmp1 = dpl[i-2][j-1];
                    if (i+a[j]+1<=N+1) tmp2 = dpr[i+a[j]+1][j+1];
                    if (tmp1 && tmp2){
                        for (int k=max(prv+a[j], i);k<i+a[j];k++)ans[k-1] = 'X';
                        prv = i;
                    }
                }
            }
        }
    }
    for (int i=1;i<=N;i++){
        for (int j=0;j<=K;j++) if (str[i]!='X' && dpl[i-1][j] && dpr[i+1][j+1]){
            if (ans[i-1]=='X' || ans[i-1]=='?') ans[i-1] = '?';
            else ans[i-1] = '_';
        }
    }
    for (int i=0;i<N;i++) assert(ans[i]);
    return ans;
}

• 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