Submission #1224689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224689		maya_s	Paint By Numbers (IOI16_paint)	C++20	0 / 100	0 ms	320 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;

ll dp[200200][110];
ll pref[200200][110];

pair<vector<ll>, vector<ll>> calc_l(ll n, ll k, vector<ll> &v, vector<ll> &c){
    ll j = 0, cnt = 0, lim = -1;
    vector<ll> ans(n);
    vector<ll> left_lim(n);
    for(ll i = 0; i < n; i++){
        if(cnt == c[j]) {ans[i] = ans[i-1] + 1, lim = (!v[i] ? i : lim), left_lim[i] = lim, cnt = 0, j++; continue;}
        if(v[i]) cnt++;
        else cnt = 0, lim = i;
        ans[i] = (i ? ans[i-1] : 0);
        left_lim[i] = lim;
    }
    return {ans, left_lim};
}

pair<vector<ll>, vector<ll>> calc_r(ll n, ll k, vector<ll> &v, vector<ll> &c){
    ll j = k-1, cnt = 0, lim = n;
    vector<ll> ans(n);
    vector<ll> right_lim(n);
    for(ll i = n-1; i >= 0; i--){
        if(cnt == c[j]) {ans[i] = ans[i+1] + 1, lim = (!v[i] ? i : lim), right_lim[i] = lim, cnt = 0, j--; continue;}
        if(v[i]) cnt++;
        else cnt = 0, lim = i;
        ans[i] = (i < n-1 ? ans[i+1] : 0);
        right_lim[i] = lim;
    }
    return {ans, right_lim};
}

string solve_puzzle(string s, vector<int> c) {
    ll n = s.size(), k = c.size();
    vector<ll> v(n);
    for(ll i = 0; i < n; i++) {
        if(s[i] == '.') v[i] = 2;
        else if(s[i] == '_') v[i] = 0;
        else v[i] = 1;
    }
    auto[left_cnt, left_lim] = calc_l(n, k, v, c);
    auto[right_cnt, right_lim] = calc_r(n, k, v, c);
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < k; j++){
            dp[i][j] = ((left_lim[i] != i - c[j] + 1) && s[i - c[j]] != 'X' && pref[i - c[j]][j]);
            pref[i+1][j+1] += dp[i][j];
        }
    }
    string ans = s;
    for(ll i = 0; i < n; i++){
        if(s[i] != '.') continue;
        bool white = (left_cnt[i] + right_cnt[i] >= k);
        bool black = 0;
        for(ll j = 0; j < k; j++) if(pref[i + c[j]][j+1] - pref[i][j]) black = 1;
        if(!white) ans[i] = 'X';
        else if(!black) ans[i] = '_';
        else ans[i] = '?';
    }
    return ans;
}

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: 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