Submission #1225461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225461		Hamed_Ghaffari	Paint By Numbers (IOI16_paint)	C++20	100 / 100	298 ms	42688 KiB

paint

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

const int MXN = 2e5+5;
const int MXK = 102;

int n, p_[MXN], ps[MXN];
bool pre[MXN][MXK], suf[MXN][MXK];

string solve_puzzle(string s, vector<int> c) {
    int n = s.size(), k = c.size();
    s = "#" + s;
    for(int i=1; i<=n; i++)
        p_[i] = p_[i-1] + (s[i]=='_');
    pre[0][0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=k; j++) {
            pre[i][j] |= pre[i-1][j]&&(s[i]!='X');
            if(j==1)
                pre[i][j] |= i>=c[0] && !(p_[i]-p_[i-c[0]]) && pre[i-c[0]][0];
            else if(j>1)
                pre[i][j] |= i>=c[j-1]+1 && !(p_[i]-p_[i-c[j-1]])
                && (s[i-c[j-1]]!='X') && pre[i-c[j-1]-1][j-1];
        }
    suf[n+1][0] = 1;
    for(int i=n; i>=1; i--)
        for(int j=0; j<=k; j++) {
            suf[i][j] |= suf[i+1][j]&&(s[i]!='X');
            if(j==1)
                suf[i][j] |= i+c[k-1]<=n+1 && !(p_[i+c[k-1]-1]-p_[i-1]) && suf[i+c[k-1]][0];
            else if(j>1)
                suf[i][j] |= i+c[k-j]<=n && !(p_[i+c[k-j]-1]-p_[i-1])
                && (s[i+c[k-j]]!='X') && suf[i+c[k-j]+1][j-1];
        }
    for(int i=0; i<k; i++)
        for(int l=0, r=c[i]+1; r<=n+1; l++, r++)
            if(!(p_[r-1]-p_[l]) && (l==0||s[l]!='X') && (r==n+1||s[r]!='X'))
                if(l==0 ? (i==0) : pre[l-1][i])
                    if(r==n+1 ? (i==k-1) : suf[r+1][k-1-i])
                        ps[l+1]++,
                        ps[r]--;
    string ans(n, '?');
    for(int i=1; i<=n; i++) {
        ps[i] += ps[i-1];
        if(s[i]=='.') {
            bool b = 0;
            for(int j=0; j<=k; j++)
                b |= pre[i-1][j] && suf[i+1][k-j];
            if(b && ps[i]) ans[i-1] = '?';
            else if(b) ans[i-1] = '_';
            else ans[i-1] = 'X';
        }
        else ans[i-1] = s[i];
    }
    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