oj.uz

Submission #92622

# Submission time Handle Problem Language Result Execution time Memory
92622 2019-01-04T05:26:41 Z kitsu_hi Paint By Numbers (IOI16_paint) C++14
32 / 100
 3 ms 892 KB 
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'

int frsB = -1;
int dp[2005][105][3];
bool Black[2005];
bool White[2005];
int c1[105];

bool used[2005][105][2];

void find ( string ss ) {
    int ll = ss.size();
    for ( int i = 0; i < ll; i++ ) {
        if ( ss[i] == 'X' && frsB == -1 ) {
            frsB = i;
        }
    }
    if ( frsB == -1 ) {
        frsB = 1000000000;
    }
}

void go ( int clr, int num, int pos ) {
    if( used[pos][num][clr] != 0 ) return;
    used[pos][num][clr] = 1;
    if( num == 0 && clr == 1 ) return;
    if( pos < 0 ) return;
    if ( clr == 0 ) {
        White[pos] = 1;
        if ( dp[pos - 1][num][0] == 1 ) go( 0, num, pos - 1);
        if ( dp[pos - 1][num][1] == 1 ) go( 1, num, pos - 1);
        return;
    }
    if ( clr == 1 ) {
        for ( int i = pos; i >= pos - c1[num - 1] + 1; i-- ) Black[i] = 1;
        go ( 0, num - 1, pos - c1[num - 1] );
        return;
    }
}

string solve_puzzle( string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    for ( int i = 0; i < k; i++ ) {
        c1[i] = c[i];
    }
    find ( s );
    
    int cntW = 0;
    for ( int i = 0; i < c[0]; i++ ) {
        if ( s[i] == '_' ) {
            cntW++;
        }
    }
    for ( int i = 0; i < c[0] - 1; i++ ) {
        dp[i][1][1] = 0;
    }
    for ( int i = 0; i <= min( frsB, n - c[0] ); i++ ){
        if ( cntW == 0 ) {
            dp[c[0] + i - 1][1][1] = 1;
        }
        else {
            dp[c[0] + i - 1][1][1] = 0;
        }
        if ( s[c[0] + i] == '_' ) {
            cntW--;
        }
        if ( s[i] == '_' ) {
            cntW--;
        }
    }
    for ( int i = min( frsB, n - c[0] ) + c[0]; i < n; i++ ) {
        dp[i][1][1] = 0;
    }
    for ( int i = 0; i < c[0]; i++ ) {
        dp[i][1][0] = 0;
    }
    if ( dp[c[0] - 1][1][1] == 1 && s[c[0]] != 'X' ) {
        dp[c[0]][1][0] = 1;
    } 
    for ( int i = c[0] + 1; i < n; i++ ){
        if ( s[i] == 'X' ) {
            dp[i][1][0] = 0;
        }
        else {
            if ( dp[i - 1][1][0] || dp[i - 1][1][1] ) {
                dp[i][1][0] = 1;
            }
            else {
                dp[i][1][0] = 0;
            }
        }
    }

    for ( int i = 2; i <= k; i++ ) {
        cntW = 0;
        for ( int j = 0; j < c[i - 1]; j++ ) {
            if ( s[j] == '_' ) {
                cntW++;
            }
        }
        for ( int j = 0; j < c[i - 1]; j++ ) {
            dp[j][i][1] = 0;
        }
        for ( int j = c[i - 1]; j < n; j++ ) {
            if ( s[j] == '_' ) {
                cntW++;
            }
            if ( s[j - c[i - 1]] == '_' ) {
                cntW--;
            }
            dp[j][i][1] = 0;
            if ( cntW == 0 && dp[j - c[i - 1]][i - 1][0] ) {
                dp[j][i][1] = 1;
            } 
        
        }
        dp[0][i][0] = 0;
        for ( int j = 1; j < n; j++ ) {
            dp[j][i][0] = 0;
            if ( s[j] != 'X' && (dp[j - 1][i][1] || dp[j - 1][i][0]) ) {
                dp[j][i][0] = 1;
            }
        }
    }
    memset( Black, 0, sizeof Black);
    memset( White, 0, sizeof White);
    memset( used, 0, sizeof used );

    if( dp[n - 1][k][1] == 1 ) go( 1, k, n - 1);
    if( dp[n - 1][k][0] == 1 ) go( 0, k, n - 1);
    for ( int i = 0; i < n; i++ ) {
        if ( Black[i] == 1 && White[i] == 1 ){
            s[i] = '?';
        }
        if ( Black[i] == 1 && White[i] == 0 ){
            s[i] = 'X';
        }
        if ( Black[i] == 0 && White[i] == 1 ){
            s[i] = '_';
        }
    }
    return s;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10
20 Correct 2 ms 888 KB n = 100, m = 5
21 Correct 2 ms 888 KB n = 90, m = 3
22 Correct 2 ms 892 KB n = 86, m = 2
23 Correct 2 ms 888 KB n = 81, m = 4
24 Correct 2 ms 888 KB n = 89, m = 10
25 Correct 2 ms 760 KB n = 81, m = 23
26 Correct 2 ms 888 KB n = 86, m = 8
27 Correct 2 ms 760 KB n = 53, m = 22
28 Correct 2 ms 888 KB n = 89, m = 35
29 Correct 2 ms 760 KB n = 63, m = 25
30 Correct 2 ms 888 KB n = 100, m = 50
31 Correct 2 ms 888 KB n = 99, m = 50

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10
20 Correct 2 ms 888 KB n = 100, m = 5
21 Correct 2 ms 888 KB n = 90, m = 3
22 Correct 2 ms 892 KB n = 86, m = 2
23 Correct 2 ms 888 KB n = 81, m = 4
24 Correct 2 ms 888 KB n = 89, m = 10
25 Correct 2 ms 760 KB n = 81, m = 23
26 Correct 2 ms 888 KB n = 86, m = 8
27 Correct 2 ms 760 KB n = 53, m = 22
28 Correct 2 ms 888 KB n = 89, m = 35
29 Correct 2 ms 760 KB n = 63, m = 25
30 Correct 2 ms 888 KB n = 100, m = 50
31 Correct 2 ms 888 KB n = 99, m = 50
32 Correct 2 ms 760 KB n = 13, m = 4
33 Correct 2 ms 888 KB n = 86, m = 2
34 Incorrect 2 ms 888 KB char #12 differ - expected: '?', found: '_'
35 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10
20 Correct 2 ms 888 KB n = 100, m = 5
21 Correct 2 ms 888 KB n = 90, m = 3
22 Correct 2 ms 892 KB n = 86, m = 2
23 Correct 2 ms 888 KB n = 81, m = 4
24 Correct 2 ms 888 KB n = 89, m = 10
25 Correct 2 ms 760 KB n = 81, m = 23
26 Correct 2 ms 888 KB n = 86, m = 8
27 Correct 2 ms 760 KB n = 53, m = 22
28 Correct 2 ms 888 KB n = 89, m = 35
29 Correct 2 ms 760 KB n = 63, m = 25
30 Correct 2 ms 888 KB n = 100, m = 50
31 Correct 2 ms 888 KB n = 99, m = 50
32 Correct 2 ms 760 KB n = 13, m = 4
33 Correct 2 ms 888 KB n = 86, m = 2
34 Incorrect 2 ms 888 KB char #12 differ - expected: '?', found: '_'
35 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10
20 Correct 2 ms 888 KB n = 100, m = 5
21 Correct 2 ms 888 KB n = 90, m = 3
22 Correct 2 ms 892 KB n = 86, m = 2
23 Correct 2 ms 888 KB n = 81, m = 4
24 Correct 2 ms 888 KB n = 89, m = 10
25 Correct 2 ms 760 KB n = 81, m = 23
26 Correct 2 ms 888 KB n = 86, m = 8
27 Correct 2 ms 760 KB n = 53, m = 22
28 Correct 2 ms 888 KB n = 89, m = 35
29 Correct 2 ms 760 KB n = 63, m = 25
30 Correct 2 ms 888 KB n = 100, m = 50
31 Correct 2 ms 888 KB n = 99, m = 50
32 Correct 2 ms 760 KB n = 13, m = 4
33 Correct 2 ms 888 KB n = 86, m = 2
34 Incorrect 2 ms 888 KB char #12 differ - expected: '?', found: '_'
35 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB n = 13, m = 1
2 Correct 2 ms 764 KB n = 18, m = 1
3 Correct 2 ms 760 KB n = 17, m = 1
4 Correct 2 ms 760 KB n = 1, m = 1
5 Correct 2 ms 760 KB n = 20, m = 1
6 Correct 2 ms 760 KB n = 20, m = 1
7 Correct 2 ms 760 KB n = 20, m = 1
8 Correct 2 ms 760 KB n = 20, m = 5
9 Correct 2 ms 760 KB n = 18, m = 3
10 Correct 2 ms 760 KB n = 17, m = 2
11 Correct 2 ms 760 KB n = 20, m = 2
12 Correct 2 ms 760 KB n = 17, m = 4
13 Correct 3 ms 760 KB n = 17, m = 6
14 Correct 2 ms 760 KB n = 17, m = 1
15 Correct 2 ms 760 KB n = 17, m = 4
16 Correct 2 ms 760 KB n = 13, m = 3
17 Correct 2 ms 760 KB n = 18, m = 4
18 Correct 2 ms 760 KB n = 20, m = 10
19 Correct 2 ms 760 KB n = 19, m = 10
20 Correct 2 ms 888 KB n = 100, m = 5
21 Correct 2 ms 888 KB n = 90, m = 3
22 Correct 2 ms 892 KB n = 86, m = 2
23 Correct 2 ms 888 KB n = 81, m = 4
24 Correct 2 ms 888 KB n = 89, m = 10
25 Correct 2 ms 760 KB n = 81, m = 23
26 Correct 2 ms 888 KB n = 86, m = 8
27 Correct 2 ms 760 KB n = 53, m = 22
28 Correct 2 ms 888 KB n = 89, m = 35
29 Correct 2 ms 760 KB n = 63, m = 25
30 Correct 2 ms 888 KB n = 100, m = 50
31 Correct 2 ms 888 KB n = 99, m = 50
32 Correct 2 ms 760 KB n = 13, m = 4
33 Correct 2 ms 888 KB n = 86, m = 2
34 Incorrect 2 ms 888 KB char #12 differ - expected: '?', found: '_'
35 Halted 0 ms 0 KB -