Submission #868825

#	Time	Username	Problem	Language	Result	Execution time	Memory
868825		hgmhc	Paint By Numbers (IOI16_paint)	C++17	100 / 100	556 ms	126036 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(x) cerr << #x << ": " << (x) << endl

const int N = 2e5+5, K = 105;
int n, k;
char S[N]; int C[N];

int c_[N];
bool pfx[N][K], sfx[N][K];
int ctr[N][K];

void calc_fx(bool fx[N][K]) {
    // fx[i][j] := 1..i에서 앞선 j개의 블록 포함되게 가능 여부
    fx[0][0] = true;
    rep(i,1,n+1) {
        if (S[i] != 'X') fx[i][0] |= fx[i-1][0];
        rep(j,1,k) {
            if (S[i] != 'X') fx[i][j] |= fx[i-1][j];
            if (i-C[j] == 0 && j == 1) {
                if (c_[C[j]] == 0) {
                    fx[i][j] = true;
                }
            }
            else if (i-C[j] > 0) {
            // if (i == 2 && j == 1 && S[i] == '.') cerr << "F " << c_[1] << ' ' << c_[2] << endl;
                if (c_[i] - c_[i-C[j]] == 0) {
                    if (S[i-C[j]] != 'X') {
                        fx[i][j] |= fx[i-C[j]-1][j-1];
                    }
                }
            }
        }
    }
}

bool Pf(int i, int j) {
    if (i < 1) return j == 0;
    return pfx[i][j];
}
bool Sf(int i, int j) {
    if (i > n) return j == 0;
    return sfx[i][j];
}

void calc_ctr() {
    rep(j,1,k) rep(i,0,n-C[j]) {
        if (c_[i+C[j]] - c_[i] == 0) {
            if (S[i] != 'X' && S[i+C[j]+1] != 'X') {
                ctr[i+C[j]][j] = Pf(i-1,j-1) & Sf(i+C[j]+2,k-j);
            }
        }
    }
}

void precalc() {
    // pfx[i][j] := 1..i에서 앞선 j개의 블록 포함되게 가능 여부
    // sfx[i][j] := i..n에서 뒷쪽 j개의 블록 포함되게 가능 여부
    // ctr[i][j] := k=1..i에 블록 j의 오른쪽 끝이 꽂히도록 가능한 경우의 수
    rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
    calc_fx(pfx), reverse(S+1,S+n+1), reverse(C+1,C+k+1);
    rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
    calc_fx(sfx), reverse(S+1,S+n+1), reverse(C+1,C+k+1);
    rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
    
    rep(i,0,(n+1)/2) {
        rep(j,0,k) swap(sfx[i][j], sfx[n-i+1][j]);
    }
    
    calc_ctr();
    rep(i,1,k) rep(j,1,n) {
        ctr[j][i] += ctr[j-1][i];
    }
    
    // rep(i,1,n) {
    //     fprintf(stderr,"sfx[%d]: ", i);
    //     rep(j,0,k) {
    //         fprintf(stderr,"%d ", sfx[i][j]);
    //     }
    //     cerr << endl;
    // }
}

bool can_(int i) {
    bool res = false;
    rep(x,0,k) {
        // fprintf(stderr,"Pf(%d,%d)=%d\n",i-1,x,Pf(i-1,x));
        // fprintf(stderr,"Sf(%d,%d)=%d\n",i+1,k-x,Sf(i+1,k-x));
        res |= Pf(i-1,x) & Sf(i+1,k-x);
    }
    return res;
}

bool canX(int i) {
    bool res = false;
    rep(x,1,k) {
        res |= ctr[min(n,i+C[x]-1)][x] - ctr[i-1][x] > 0;
    }
    return res;
}

string solve_puzzle(string a, vi b) {
    n = siz(a), k = siz(b);
    string res(n,'$');
    
    rep(i,1,n) S[i] = a[i-1];
    rep(i,1,k) C[i] = b[i-1];
    precalc();
    
    rep(i,1,n) {
        if (S[i] != '.') {
            res[i-1] = S[i];
            continue;
        }
        bool a = canX(i);
        bool b = can_(i);
        if (a&b) res[i-1]='?';
        else if (a) res[i-1]='X';
        else if (b) res[i-1]='_';
        // else assert(0);
    }
    return res;
}

#ifdef LOCAL

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

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10