제출 #646614

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646614		Ronin13	Paint By Numbers (IOI16_paint)	C++14	90 / 100	343 ms	524288 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][3];
ll DP[200005][105][3];
ll mod[] = {998244353, 1000000007, 1000000009};
 
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size(), k = c.size();
    char ch[n + 2];
  int a[k + 1], pref[n + 1];
    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] = dp[0][0][1] = 1;
    DP[n + 1][k + 1][0] = DP[n + 1][k + 1][1] = 1;
    for(int x = 0; x < 3; 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 < 3; 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];
        }
    }
    }
    ll sum[n + 2][3];
    for(int i = 0; i <= n + 1; i++) sum[i][0] = sum[i][1] = sum[i][2] = 0;
    for(int x = 0; x < 2; 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[3];
    cursum[1] = cursum[2] = cursum[0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++) cursum[j] += sum[i][j], cursum[j] %= mod[j];
        bool ind = false;
        for(int j = 0; j < 3; j++){
            if(cursum[j] != dp[n][k][j]) ind = true;
        }
        if(!ind){
            ans += 'X';
            continue;
        }
        for(int j= 0; j < 3; j++){
            if(cursum[j]) ind = false;
        }
        if(ind){
            ans += '_';
            continue;
        }
        ans += '?';
    }
    return ans;
}

• 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