Submission #1178926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178926		vicvic	Paint By Numbers (IOI16_paint)	C++20	90 / 100	22 ms	36424 KiB

paint

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int NMAX=1e5, KMAX=100;
int dp[NMAX+5][KMAX+1], dp1[NMAX+5][KMAX+1], white[NMAX+5], black[NMAX+5], sum[NMAX+5];
string solve_puzzle (string s, vector <int> vec)
{
    int n=s.size(), k=vec.size();
    string ret;
    ret.resize (n);
    for (int i=0;i<n;i++)
    {
        sum[i+1]=sum[i]+(s[i]=='_');
    }
    dp[0][0]=dp1[n][k]=1;
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<=k;j++)
        {
            if (s[i]!='X')
                dp[i+1][j] |=dp[i][j];
            if (j<k && i+vec[j]<n && s[i+vec[j]]!='X' && sum[i]==sum[i+vec[j]])
                dp[i+vec[j]+1][j+1] |=dp[i][j];
        }
    }
    for (int i=n;i>=1;i--)
    {
        for (int j=0;j<=k;j++)
        {
            if (s[i-1]!='X')
                dp1[i-1][j] |=dp1[i][j];
            if (j && i-vec[j-1]>0 && s[i-vec[j-1]-1]!='X' && sum[i]==sum[i-vec[j-1]])
                dp1[i-vec[j-1]-1][j-1] |=dp1[i][j];
        }
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<=k;j++)
            white[i] |=dp[i+1][j] && dp1[i][j];
        for (int j=0;j<k;j++)
            if (i+vec[j]<=n && dp[i][j] && dp1[i+vec[j]][j+1] && sum[i]==sum[i+vec[j]])
            {
                black[i]++;
                black[i+vec[j]]--;
            }
        black[i+1]+=black[i];
        ret[i]=(black[i] && white[i]?'?':black[i]?'X':'_');
    }
    return ret;
}

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: 0 / 10