Submission #1224551

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

paint

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

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);
    string ans = s;
    for(ll i = 0; i < n; i++){
        if(s[i] != '.') continue;
        bool white = (left_cnt[i] + right_cnt[i] >= k);
        ll x = (left_lim[i] >= 0 ? left_cnt[left_lim[i]] : 0), y = (right_lim[i] < n ? right_cnt[right_lim[i]] : 0);
        bool black = 0;
        if(left_lim[i] == -1) black = (left_cnt[i] + (i < n-1 ? right_cnt[i+1] : 0));
        if(right_lim[i] == n && !black) black = (right_cnt[i] + (i ? left_cnt[i-1] : 0));
        if(x + y + 1 >= k){
            for(ll j = 0; j < k; j++) if(j <= x && y >= k - j - 1 && right_lim[i] - left_lim[i] - 1 >= c[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: 7 / 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