Submission #792256

#	Time	Username	Problem	Language	Result	Execution time	Memory
792256		I_Love_EliskaM_	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	340 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9+9;

const int N=105;
const int K=105;

int dp[N][K];
int dp2[N][K];
int can[N];
int cant[N];

void yes(int l, int r) {
    for(int i=l; i<=r; ++i) cant[i]=0;
}
void no(int l, int r) {
    for(int i=l;i<=r;++i) can[i]=0;
}

pi inter(pi a, pi b) {
    return {max(a.f,b.f),min(a.s,b.s)};
}

string solve_puzzle(string s, vector<int> c) {
    s+='_';
    int n=s.size();
    int k=c.size();
    if (n>101) return "";
    forn(i,n) can[i]=cant[i]=1;

    vector<vector<int>> pos(k+1);
    pos[0].pb(0);
    dp[0][0]=1;

    for(int i=1; i<=n; ++i) {
        forn(j,k) {
            int x=c[j]+1;
            if (i-x<0) continue;
            if (!pos[j].size()) continue;
            if (pos[j][0]>i-x) continue;
            int last;
            for(auto&v:pos[j]) if (v<=i-x) last=v;
            int y=1, z=1;
            for (int t=i-x; t<i-1; ++t) y&=s[t]!='_';
            y&=s[i-1]!='X';
            for (int t=last; t<i-x; ++t) z&=s[t]!='X';
            dp[i][j+1]=y&z;
            if (dp[i][j+1]) pos[j+1].pb(i);
        }
    }

    vector<vector<int>> pos2(k+2);
    pos2[k+1].pb(n+1);
    dp2[n+1][k+1]=1;
    for (int i=n; i>0; --i) {
        for(int j=k; j>0; --j) {

            int x=c[j-1]+1;
            if (i+x>n+1) continue;
            if (!pos2[j+1].size()) continue;
            if (pos2[j+1][0]<i+x) continue;
            int last;
            for(auto&v:pos2[j+1]) if (v>=i+x) last=v;
            int y=1, z=1;
            for (int t=i-1; t<i+x-2; ++t) y&=s[t]!='_';
            y&=s[i+x-2]!='X';
            for (int t=i+x-2; t<last-1; ++t) z&=s[t]!='X';
            dp2[i][j]=y&z;
            if (dp2[i][j]) pos2[j].pb(i);

        }   
    }
    
    for (int i=0; i<=n+1; ++i) dp[i][0]=dp2[i][k+1]=1;

    vector<pi> seg(k+1,{-inf,inf});    

    for (int i=1; i<=n; ++i) {
        for(int j=1; j<=k; ++j) {
            int x=c[j-1]+1;
            if (dp[i][j]) {
                if (dp2[i+1][j+1]) {
                    yes(i-x,i-2);
                    seg[j]=inter(seg[j],{i-x,i-2});
                }
            }
        }
    }
    
    string ans(n,'?');
    forn(i,n) if (cant[i]) ans[i]='_';
    for(int j=1; j<=k; ++j) {
        auto x=seg[j];
        if (x.f<=x.s) for(int i=x.f; i<=x.s; ++i) ans[i]='X';
    }
    forn(i,n) {
        if (s[i]=='X') {
            assert(ans[i]!='_');
            ans[i]='X';
        }
    }
    ans.pop_back();

    return ans;

}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:69:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |             int last;
      |                 ^~~~
paint.cpp:48:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |             int last;
      |                 ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10