oj.uz

답안 #868702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868702 2023-11-01T15:51:22 Z hgmhc Paint By Numbers (IOI16_paint) C++17
32 / 100
 1 ms 2540 KB 
#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 = 5005, K = 105;
int n, k;
char S[N]; int C[N];

int cX[N], 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) {
        rep(j,0,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 (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+2) 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') {
                    // if(i==6&&j==1)cerr<<Pf(i-1,j-1)<<' ' <<Sf(i+C[j]+2,k-j)<<endl;
                    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의 오른쪽 끝이 꽂히도록 가능한 경우의 수
    
    calc_fx(pfx);
    reverse(S+1,S+n+1);
    reverse(C+1,C+k+1);
    calc_fx(sfx);
    reverse(S+1,S+n+1);
    reverse(C+1,C+k+1);
    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) {
    //     cerr<<"sfx("<<i<<"): ";
    //     rep(j,0,k) {
    //         cerr<<sfx[i][j]<<' ';
    //     }
    //     cerr << endl;
    // }
}

bool can_(int i) {
    if (i == 1) return sfx[2][k];
    if (i == n) return pfx[n-1][k];
    bool res = false;
    rep(x,0,k) res |= pfx[i-1][x] & sfx[i+1][k-x];
    return res;
}

bool canX(int i) {
    bool res = false;
    rep(x,1,k) {
        // if (i == 7)cerr<<ctr[min(n,i+C[x]-1)][x]<<' '<<ctr[i-1][x]<<endl;
        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];
    rep(i,1,n+2) cX[i] = cX[i-1]+(S[i]=='X');
    rep(i,1,n+2) c_[i] = c_[i-1]+(S[i]=='_');
    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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10
20 Correct 1 ms 2396 KB n = 100, m = 5
21 Correct 1 ms 2392 KB n = 90, m = 3
22 Correct 1 ms 2396 KB n = 86, m = 2
23 Correct 1 ms 2392 KB n = 81, m = 4
24 Correct 1 ms 2396 KB n = 89, m = 10
25 Correct 0 ms 2396 KB n = 81, m = 23
26 Correct 1 ms 2396 KB n = 86, m = 8
27 Correct 1 ms 2396 KB n = 53, m = 22
28 Correct 1 ms 2396 KB n = 89, m = 35
29 Correct 1 ms 2396 KB n = 63, m = 25
30 Correct 1 ms 2392 KB n = 100, m = 50
31 Correct 1 ms 2540 KB n = 99, m = 50

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10
20 Correct 1 ms 2396 KB n = 100, m = 5
21 Correct 1 ms 2392 KB n = 90, m = 3
22 Correct 1 ms 2396 KB n = 86, m = 2
23 Correct 1 ms 2392 KB n = 81, m = 4
24 Correct 1 ms 2396 KB n = 89, m = 10
25 Correct 0 ms 2396 KB n = 81, m = 23
26 Correct 1 ms 2396 KB n = 86, m = 8
27 Correct 1 ms 2396 KB n = 53, m = 22
28 Correct 1 ms 2396 KB n = 89, m = 35
29 Correct 1 ms 2396 KB n = 63, m = 25
30 Correct 1 ms 2392 KB n = 100, m = 50
31 Correct 1 ms 2540 KB n = 99, m = 50
32 Correct 1 ms 2396 KB n = 13, m = 4
33 Incorrect 1 ms 2396 KB char #2 differ - expected: 'X', found: '?'
34 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10
20 Correct 1 ms 2396 KB n = 100, m = 5
21 Correct 1 ms 2392 KB n = 90, m = 3
22 Correct 1 ms 2396 KB n = 86, m = 2
23 Correct 1 ms 2392 KB n = 81, m = 4
24 Correct 1 ms 2396 KB n = 89, m = 10
25 Correct 0 ms 2396 KB n = 81, m = 23
26 Correct 1 ms 2396 KB n = 86, m = 8
27 Correct 1 ms 2396 KB n = 53, m = 22
28 Correct 1 ms 2396 KB n = 89, m = 35
29 Correct 1 ms 2396 KB n = 63, m = 25
30 Correct 1 ms 2392 KB n = 100, m = 50
31 Correct 1 ms 2540 KB n = 99, m = 50
32 Correct 1 ms 2396 KB n = 13, m = 4
33 Incorrect 1 ms 2396 KB char #2 differ - expected: 'X', found: '?'
34 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10
20 Correct 1 ms 2396 KB n = 100, m = 5
21 Correct 1 ms 2392 KB n = 90, m = 3
22 Correct 1 ms 2396 KB n = 86, m = 2
23 Correct 1 ms 2392 KB n = 81, m = 4
24 Correct 1 ms 2396 KB n = 89, m = 10
25 Correct 0 ms 2396 KB n = 81, m = 23
26 Correct 1 ms 2396 KB n = 86, m = 8
27 Correct 1 ms 2396 KB n = 53, m = 22
28 Correct 1 ms 2396 KB n = 89, m = 35
29 Correct 1 ms 2396 KB n = 63, m = 25
30 Correct 1 ms 2392 KB n = 100, m = 50
31 Correct 1 ms 2540 KB n = 99, m = 50
32 Correct 1 ms 2396 KB n = 13, m = 4
33 Incorrect 1 ms 2396 KB char #2 differ - expected: 'X', found: '?'
34 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB n = 13, m = 1
2 Correct 1 ms 2392 KB n = 18, m = 1
3 Correct 1 ms 2396 KB n = 17, m = 1
4 Correct 1 ms 2500 KB n = 1, m = 1
5 Correct 1 ms 2396 KB n = 20, m = 1
6 Correct 0 ms 2396 KB n = 20, m = 1
7 Correct 0 ms 2396 KB n = 20, m = 1
8 Correct 0 ms 2396 KB n = 20, m = 5
9 Correct 1 ms 2396 KB n = 18, m = 3
10 Correct 1 ms 2392 KB n = 17, m = 2
11 Correct 0 ms 2396 KB n = 20, m = 2
12 Correct 0 ms 2496 KB n = 17, m = 4
13 Correct 1 ms 2396 KB n = 17, m = 6
14 Correct 0 ms 2396 KB n = 17, m = 1
15 Correct 0 ms 2396 KB n = 17, m = 4
16 Correct 0 ms 2392 KB n = 13, m = 3
17 Correct 1 ms 2396 KB n = 18, m = 4
18 Correct 1 ms 2396 KB n = 20, m = 10
19 Correct 1 ms 2396 KB n = 19, m = 10
20 Correct 1 ms 2396 KB n = 100, m = 5
21 Correct 1 ms 2392 KB n = 90, m = 3
22 Correct 1 ms 2396 KB n = 86, m = 2
23 Correct 1 ms 2392 KB n = 81, m = 4
24 Correct 1 ms 2396 KB n = 89, m = 10
25 Correct 0 ms 2396 KB n = 81, m = 23
26 Correct 1 ms 2396 KB n = 86, m = 8
27 Correct 1 ms 2396 KB n = 53, m = 22
28 Correct 1 ms 2396 KB n = 89, m = 35
29 Correct 1 ms 2396 KB n = 63, m = 25
30 Correct 1 ms 2392 KB n = 100, m = 50
31 Correct 1 ms 2540 KB n = 99, m = 50
32 Correct 1 ms 2396 KB n = 13, m = 4
33 Incorrect 1 ms 2396 KB char #2 differ - expected: 'X', found: '?'
34 Halted 0 ms 0 KB -