Submission #1044793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044793		ProtonDecay314	Paint By Numbers (IOI16_paint)	C++17	90 / 100	592 ms	524288 KiB

paint

#include "paint.h"

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

bool poss(int i, int ci, const string& s, const vi& c, const vi& prev_x, const vi& prev_u, vvi& dp, vpi& poss_u, vpi& poss_x) {
    if(i >= -2 && ci == -1) {
        if(i < 0 || prev_x[i] == -1) {
            if(i >= 0) poss_u.pb({0, i});
            return true;
        } else return false;
    }
    if(i < 0) return false;
    if(ci != -1 && c[ci] > i + 1) return false;

    int& ans = dp[i][ci];
    
    if(ans == -1) {
        bool poss_cur_u = s[i] != 'X' && poss(i - 1, ci, s, c, prev_x, prev_u, dp, poss_u, poss_x);

        if(poss_cur_u) poss_u.pb({i, i});
        
        // Recursive case: current is x

        bool poss_cur_x = (i - c[ci] < 0 || s[i - c[ci]] != 'X') && prev_u[i] <= i - c[ci] && poss(i - c[ci] - 1, ci - 1, s, c, prev_x, prev_u, dp, poss_u, poss_x);

        if(poss_cur_x) {
            if(i - c[ci] >= 0) poss_u.pb({i - c[ci], i - c[ci]});
            poss_x.pb({max(i - c[ci] + 1, 0), i});
        }

        ans = (poss_cur_u || poss_cur_x ? 1 : 0);
    }

    return (bool)ans;
}

string solve_puzzle(string s, vi c) {
    int n = s.size();
    int k = c.size();

    vvi dp;
    for(int i = 0; i < n; i++) {
        vi dpr(k, -1);
        dp.pb(dpr);
    }

    vi prev_u(n, -1);
    vi prev_x(n, -1);

    for(int i = 0; i < n; i++) {
        if(i > 0) {
            prev_u[i] = prev_u[i - 1];
            prev_x[i] = prev_x[i - 1];
        }
        if(s[i] == '_') prev_u[i] = i;
        if(s[i] == 'X') prev_x[i] = i;
    }

    vpi poss_u;
    vpi poss_x;

    poss(n - 1, k - 1, s, c, prev_x, prev_u, dp, poss_u, poss_x);

    vi u_pref(n + 1, 0);
    vi x_pref(n + 1, 0);

    for(pi inds: poss_u) {
        u_pref[inds.fi]++;
        u_pref[inds.se + 1]--;
    }
    for(pi inds: poss_x) {
        x_pref[inds.fi]++;
        x_pref[inds.se + 1]--;
    }

    int us = 0;
    int xs = 0;

    string ans;

    for(int i = 0; i < n; i++) {
        us += u_pref[i];
        xs += x_pref[i];

        if(us > 0 && xs > 0) ans.pb('?');
        else if(us > 0) ans.pb('_');
        else ans.pb('X');
    }

    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