Submission #646757

#	Time	Username	Problem	Language	Result	Execution time	Memory
646757		Ronin13	Paint By Numbers (IOI16_paint)	C++14	100 / 100	678 ms	332748 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
#include <cstdlib>
using namespace std;
 
ll dp[200005][105][1];
ll DP[200005][105][1];
ll mod[] = {998244353, 1000000007};
char ch[200005];
int a[2000005], pref[200005];
int sum[200005][2];
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size(), k = c.size();
    ch[0] = ch[n + 1] = '.';
    for(int i = 1; i<= n; i++){
        ch[i] = s[i - 1];
    }
    for(int i = 1; i <= k; i++) a[i] = c[i - 1];
    pref[0] = 0;
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1];
        if(ch[i] == '_') pref[i]++;
    }
    dp[0][0][0]  = 1;
    DP[n + 1][k + 1][0] = 1;
    for(int x = 0; x < 1; x++){
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            if(ch[i] != 'X') dp[i][j][x] += dp[i - 1][j][x];
            if(j == 0) continue;
            if(i < a[j]) continue;
            int v = pref[i] - pref[i - a[j]];
            if(v == 0 && ch[i - a[j]] != 'X'){
                dp[i][j][x] += dp[max(0, i - a[j] - 1)][j - 1][x];
            }
            dp[i][j][x] %= mod[x];
        }
    }
    }
    for(int x = 0; x < 1; x++){
    for(int i = n; i >= 1; i--){
        for(int j = 1; j <= k + 1; j++){
            if(ch[i] != 'X') DP[i][j][x] += DP[i + 1][j][x];
            if(j == k + 1) continue;
            if(i + a[j] - 1 > n) continue;
            int v = pref[i + a[j] - 1] - pref[i - 1];
            if(v == 0 && ch[i + a[j]] != 'X'){
                DP[i][j][x] += DP[min(n + 1, i + a[j] + 1)][j + 1][x];
            }
            DP[i][j][x] %= mod[x];
        }
    }
    }
 
    for(int i = 0; i <= n + 1; i++) sum[i][0] = sum[i][1] = 0;
    for(int x = 0; x < 1; x++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(i < a[j]) continue;
            if(ch[i - a[j]] != 'X' && ch[i + 1] != 'X'){
                if(pref[i] - pref[i - a[j]]) continue;
                ll val = dp[max(i - a[j] - 1, 0)][j - 1][x] * DP[min(i + 2, n + 1)][j + 1][x];
                val %= mod[x];
                int l = i - a[j] + 1, r = i + 1;
                sum[l][x] += val;
                sum[l][x] %= mod[x];
                sum[r][x] -= val;
                sum[r][x] += mod[x];
                sum[r][x] %= mod[x];
            }
        }
    }}
    /*for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            cout << dp[i][j] << ' ';
        }
        cout << "\n";
    }*/
    string ans = "";
    ll cursum = sum[0][0];
    ll cursum1 = sum[0][1];
    for(int i = 1; i <= n; i++){
        cursum += sum[i][0];
        //cursum1 += sum[i][1];
        cursum %= mod[0]; cursum += mod[0]; cursum %= mod[0];
        //cursum1 %= mod[1]; cursum1 += mod[1]; cursum1 %= mod[1];
        if(cursum == 0 ) {ans += '_'; continue;}
        if((cursum == dp[n][k][0])){ans += 'X'; continue;}
 
        ans += '?';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:89:8: warning: unused variable 'cursum1' [-Wunused-variable]
   89 |     ll cursum1 = sum[0][1];
      |        ^~~~~~~

• 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