Submission #862514

#	Time	Username	Problem	Language	Result	Execution time	Memory
862514		hgmhc	Paint By Numbers (IOI16_paint)	C++17	32 / 100	61 ms	612 KiB

paint

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#define ensure(...) if (!(__VA_ARGS__)){ fprintf(stderr,"Error in %dth line.", __LINE__), exit(-1); }

const int N = 103, K = 103;
int n, k;

bool valid(const string &s, const vi &c) {
    bool dp[N][K]{};
    int _pfx[N]{};
    rep(i,1,n) _pfx[i]=_pfx[i-1]+(s[i]=='_');
    
    rep(i,1,n) {
        if (s[i] == 'X') {
            rep(j,i,i+c[1]-1) {
                if (s[j] == '_') break;
                if (c[1] <= j and _pfx[j]-_pfx[j-c[1]] == 0)
                    dp[j][1] = true;
            }
            break;
        }
        if (i >= c[1] and _pfx[i]-_pfx[i-c[1]] == 0) {
            dp[i][1] = true;
        }
    }
    
    rep(i,1,n) if (s[i] != '_') {
        rep(j,2,k) {
            bool flag = 1;
            per(x,i-c[j]+1,i) if (s[x] == '_') flag = 0;
            if (s[i-c[j]] == 'X') flag = 0;
            if (!flag) continue;
            per(x,1,i-c[j]-1) {
                if (s[x] == '_') break;
                dp[i][j] |= dp[x][j-1];
            }
        }
    }
    
    // rep(i,1,n) rep(j,1,k) cerr << dp[i][j] << " \n"[j == k];
    
    per(i,1,n) {
        if (i < n and s[i+1] == 'X') break;
        if (dp[i][k]) return true;
    }
    return false;
}

string solve_puzzle(string s, vi c) {
    n = siz(s), k = siz(c);
    s = "$"+s, c.insert(begin(c),0);
    string res(n,'$');
    
    // valid("$X.._._....",c);
    
    rep(i,1,n) {
        char x = s[i];
        if (x != '.') {
            res[i-1] = x;
            continue;
        }
        s[i] = 'X'; if (not valid(s,c)) res[i-1] = '_';
        s[i] = '_'; if (not valid(s,c)) res[i-1] = 'X';
        if (res[i-1] == '$') res[i-1] = '?';
        s[i] = x;
    }
    
    return res;
}

#ifdef LOCAL

const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    ensure(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    ensure(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        ensure(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);

    printf("%s\n", ans.data());
    return 0;
}

#endif

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10