Submission #1044940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044940		ProtonDecay314	Paint By Numbers (IOI16_paint)	C++17	90 / 100	589 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;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#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--)

const int MAX_BITSET_SIZE = 200000 * 100;

bool poss(int i, int ci, const string& s, const vi& c, const vi& prev_x, const vi& prev_u, bitset<MAX_BITSET_SIZE>& dp, bitset<MAX_BITSET_SIZE>& dpvis, vpi& poss_u, vpi& poss_x) {
    int k = c.size();
    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 < -2 && ci == -1) return false;
    if(i < 0) return false;
    if(ci != -1 && c[ci] > i + 1) return false;

    int dpind = i * k + ci;

    if(!dpvis[dpind]) {
        bool poss_cur_u = s[i] != 'X' && poss(i - 1, ci, s, c, prev_x, prev_u, dp, dpvis, 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, dpvis, 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});
        }

        dp[dpind] = poss_cur_u || poss_cur_x;
        dpvis[dpind] = true;
    }

    return dp[dpind];
}

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

    // vvb dp;
    // vvb dpvis;
    // for(int i = 0; i < n; i++) {
    //     vb dpr(k, false);
    //     vb dpvisr(k, false);
    //     dp.pb(dpr);
    //     dpvis.pb(dpvisr);
    // }

    bitset<MAX_BITSET_SIZE> dp;
    bitset<MAX_BITSET_SIZE> dpvis;

    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;

    vi c_pref(n, 0);

    for(int i = 0; i < k; i++) {
        if(i == 0) c_pref[i] = c[i];
        else c_pref[i] = c_pref[i - 1] + c[i] + 1;
    }

    // for(int i = 0; i < n; i++) {
    //     for(int ci = 0; ci < k; ci++) {
    //         if(i < c_pref[ci] + 3) continue;
    //         poss(i, ci, s, c, prev_x, prev_u, dp, dpvis, poss_u, poss_x);
    //     }
    // }

    poss(n - 1, k - 1, s, c, prev_x, prev_u, dp, dpvis, 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