Submission #291650

#	Time	Username	Problem	Language	Result	Execution time	Memory
291650		peti1234	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	384 KiB

paint

#include <bits/stdc++.h>

using namespace std;
const int c=200002, p=102;
int n, k, kom[c], dp[c];
string ans;
bool kezd[c][p], veg[c][p], v[c];
string solve_puzzle(string s, vector<int> sz) {
    n=s.size(), k=sz.size();
    s+='.';
    for (int i=0; i<n; i++) kom[i+1]=(s[i]=='_')+kom[i];
    kezd[0][0]=1;
    for (int i=0; i<=n; i++) for (int j=0; j<=k; j++) if (kezd[i][j]) {
        if (s[i]!='X') kezd[i+1][j]=1;
        if (j<k) {
            int h=sz[j];
            if (i+h<=n && kom[i+h]==kom[i] && s[i+h]!='X') kezd[i+h+1][j+1]=1;
        }
    }
    veg[n][k]=1;
    for (int i=n; i>=1; i--) for (int j=k; j>=0; j--) if (veg[i][j]) {
        if (s[i-1]!='X') veg[i-1][j]=1;
        if (j) {
            int h=sz[j-1];
            if (i-h>=0 && kom[i]==kom[i-h]) veg[i-h][j-1]=1;
        }
    }
    for (int i=1; i<=n; i++) for (int j=0; j<=k; j++) {
        if (kezd[i][j] && veg[i][c]) v[i]=1;
        if (j<k) {
            int h=sz[j];
            if (i+h<=n && kom[i+h]==kom[i] && s[i+h]!='X' && kezd[i][j] && veg[i+h+1][j+1]) dp[i]++, dp[i+h]--;
        }
    }
    for (int i=1; i<=n; i++) {
        dp[i]+=dp[i-1];
        if (v[i] && dp[i]) ans+='?';
        if (v[i] && !dp[i]) ans+='_';
        if (!v[i] && dp[i]) ans+='X';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:29:35: warning: array subscript 200002 is above array bounds of 'bool [102]' [-Warray-bounds]
   29 |         if (kezd[i][j] && veg[i][c]) v[i]=1;
      |                           ~~~~~~~~^

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