Submission #159405

#	Time	Username	Problem	Language	Result	Execution time	Memory
159405		rama_pang	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1364 ms	196580 KiB

paint

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

string S;
int N, K;
vector<int> C;
vector<int> pref_white, pref_black, ans;
bitset<200000> can_white, can_black;
int memo[200000][100][2];

struct disj {
    vector<int> p;

    void init(int n) {
        p.resize(n + 1);
        iota(p.begin(), p.end(), 0);
    }
    
    int par(int n) {
        return (p[n] == n)? n : p[n] = par(p[n]);
    }
    
    void join(int le, int ri) {
        if (ri >= p.size()) return;
        le = par(le);
        ri = par(ri);
        if (le == ri) return;
        p[le] = ri;
    }
    
} hop_white, hop_black;

inline bool check_white(int le, int ri) { //get number of forced whites in le...ri
    if (ri >= N) return false;
    if (le > ri) return true;
    int res = pref_white[ri];
    if (le > 0) res -= pref_white[le - 1]; 
    return (res == 0);
}

inline bool check_black(int le, int ri) { //get number of forced blacks in le...ri
    if (ri >= N) return false;
    if (le > ri) return true;
    int res = pref_black[ri];
    if (le > 0) res -= pref_black[le - 1]; 
    return (res == 0);
}

inline void update(int le, int ri, disj &d, bitset<200000> &can) { //update segment le...ri
    for (int i = le; i <= ri;) {
        can[i] = 1;
        d.join(i, i + 1);
        i = d.par(i);
    }
}

bool dp(int n, int k, int last_black) {
    if (k == K) {
        if (check_black(n, N - 1)) {
            update(n, N - 1, hop_white, can_white);
            return true;
        } else {
            return false;
        }
    }

    if (n == N) return false;

    if (memo[n][k][last_black] != -1) return memo[n][k][last_black];

    bool ret = false;

    if (S[n] == '_') {
        update(n, n, hop_white, can_white);
        ret = dp(n + 1, k, 0);
    } else if (S[n] == 'X') {
        update(n, n, hop_black, can_black);
        if (!last_black && check_white(n, n + C[k] - 1)) {
            ret = dp(n + C[k], k + 1, 1);
            if (ret) update(n, n + C[k] - 1, hop_black, can_black);
        }
    } else {
        bool resW = false, resB = false;

        resW = dp(n + 1, k, 0);
        if (!last_black && check_white(n, n + C[k] - 1)) resB = dp(n + C[k], k + 1, 1);
        
        if (resW) update(n, n, hop_white, can_white);
        if (resB) update(n, n + C[k] - 1, hop_black, can_black);

        ret = (resW || resB);
    }

    return memo[n][k][last_black] = ret;
}

string solve_puzzle(string s, vector<int> c) {
    S = s, N = s.size(), K = c.size(), C = c;
    pref_white.resize(N), pref_black.resize(N), ans.resize(N);
    hop_white.init(N), hop_black.init(N);

    for (int i = 0; i < N; i++) {
        pref_white[i] = (S[i] == '_')? 1 : 0;
        if (i > 0) pref_white[i] += pref_white[i - 1];

        pref_black[i] = (S[i] == 'X')? 1 : 0;
        if (i > 0) pref_black[i] += pref_black[i - 1];
    }

    memset(memo, -1, sizeof(memo));
    dp(0, 0, 0);

    string res;
    for (int i = 0; i < N; i++) {
        ans[i] = can_white[i] | (can_black[i] << 1);
        if (ans[i] == 1) {
            res.push_back('_');
        } else if (ans[i] == 2) {
            res.push_back('X');
        } else {
            res.push_back('?');
        }
    }

    return res;
}

Compilation message (stderr)

paint.cpp: In member function 'void disj::join(int, int)':
paint.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (ri >= p.size()) return;
             ~~~^~~~~~~~~~~
paint.cpp: In function 'bool dp(int, int, int)':
paint.cpp:95:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
     return memo[n][k][last_black] = ret;
            ~~~~~~~~~~~~~~~~~~~~~~~^~~~~

• 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