Submission #58451

#	Time	Username	Problem	Language	Result	Execution time	Memory
58451		FLDutchman	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1996 ms	195800 KiB

paint

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

typedef int INT;

#define pb push_back
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define int long long

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
const ll INF = 1e15;

int N, K;
vector<INT> C;
string S;
vi prefix, bprefix;

int dp[200100][110];
vi bp, wp;

int f(int i, int j){
    //cout << i << " " << j << endl;

    if(i > N+1) return 0;
    int &res = dp[i][j];
    if(res!=-1) return res;
    if(j == K) {
        if(i > N+1) return 0;
        if(i == N+1) return res = 1;
        if(bprefix[N] - bprefix[i]) return res = 0;
        wp[i]++;
        return res = 1;
    }
    if(i >= N) return res = 0;
    res = 0;
    if(i + C[j] <= N and prefix[i+C[j]] - prefix[i] == 0 and S[i+C[j]] != 'X') {
        res = f(i+C[j]+1, j+1);
        //cout<<res<<endl;
        if(res) {
            wp[i+C[j]]++;
            wp[i+C[j]+1]--;
            bp[i]++;
            bp[i+C[j]]--;
            //cout << i+C[j] << endl;
        }
    }
    if(S[i] != 'X' and f(i+1, j)){
        //cout<<"White" << endl;
        res = 1;
        wp[i]++;
        wp[i+1]--;
    }
    //cout << i << " " << j << " " << res << endl;

    return res;
}

std::string solve_puzzle(std::string s, std::vector<INT> c) {
    FOR(i, 0, 200100) FOR(j, 0, 110) dp[i][j] = -1;
    S = s;
    C = c;
    K = c.size();
    N = s.size();
    S.pb('.');
    prefix.assign(N+3, 0);
    bprefix.assign(N+3, 0);
    wp.assign(N+3, 0);
    bp.assign(N+3, 0);
    FOR(i, 1, N+3) prefix[i] = prefix[i-1] + (S[i-1] == '_');
    FOR(i, 1, N+3) bprefix[i] = bprefix[i-1] + (S[i-1] == 'X');
    f(0, 0);
    FOR(i, 1, N) bp[i] += bp[i-1];
    FOR(i, 1, N) wp[i] += wp[i-1];
    FOR(i, 1, N) if(S[i] == 'X') wp[i] = 0;
    
    string ret (N, '?');
    FOR(i, 0, N) {
        if(!wp[i]) ret[i] = 'X';
        else if(!bp[i]) ret[i] = '_';
    }
    return ret;
}

/*
........
2 3 4

..._._....
1 3

.X........
1 3



*/

• 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: 10 / 10