Submission #1010806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010806		LucaIlie	Red-blue table (IZhO19_stones)	C++17	100 / 100	41 ms	2900 KiB

stones

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000;
char mat[MAX_N][MAX_N], aux[MAX_N][MAX_N];
int sumL[MAX_N], sumC[MAX_N];

int eval( int n, int m ) {
    for ( int l = 0; l < n; l++ )
        sumL[l] = 0;
    for ( int c = 0; c < m; c++ )
        sumC[c] = 0;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            sumL[l] += (mat[l][c] == '+' ? 1 : -1);
            sumC[c] += (mat[l][c] == '+' ? -1 : +1);
        }
    }
    int r = 0;
    for ( int l = 0; l < n; l++ )
        r += (sumL[l] > 0);
    for ( int c = 0; c < m; c++ )
        r += (sumC[c] > 0);
    return r;
}

int solve1( int n, int m ) {
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l == n - 1 && m != 1 )
                mat[l][c] = '-';
            else {
                if ( l < n / 2 ) {
                    if ( c <= m / 2 )
                        mat[l][c] = '+';
                    else
                        mat[l][c] = '-';
                } else {
                    if ( c < (m - 1) / 2 )
                        mat[l][c] = '-';
                    else
                        mat[l][c] = '+';
                }
            }
        }
    }
    return eval( n, m );
}

int solve2( int n, int m ) {
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l >= n - 2 && m != 1 )
                mat[l][c] = '-';
            else {
                if ( l < (n - 1) / 2 ) {
                    if ( c <= m / 2 )
                        mat[l][c] = '+';
                    else
                        mat[l][c] = '-';
                } else {
                    if ( c < (m - 1) / 2 )
                        mat[l][c] = '-';
                    else
                        mat[l][c] = '+';
                }
            }
        }
    }
    return eval( n, m );
}

int solve3( int n, int m ) {
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( n > m ) {
                if ( c <= m / 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            } else {
                if ( l <= n / 2 )
                    mat[l][c] = '-';
                else
                    mat[l][c] = '+';
            }
        }
    }
    return eval( n, m );
}

int solve4( int n, int m ) {
    if ( n != 6 || m != 6 )
        return 0;

    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l < 3 )
                mat[l][c] = '-';
            else if ( l == 3 ) {
                if ( c < 4 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else if ( l == 4 ) {
                if ( c < 2 || c >= 4 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else if ( l == 5 ) {
                if ( c >= 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
        }
    }
    return eval( n, m );
}

int solve5( int n, int m ) {
    bool transposed = false;
    if ( n > m ) {
        swap( n, m );
        transposed = true;
    }

    int specialLines = n / 2 + 1;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l >= specialLines )
                mat[l][c] = '-';
            else if ( l == 0 ) {
                if ( c < m / 2 + 1 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else if ( l <= specialLines / 2 ) {
                if ( c < (m + 1) / 2 - 1 || c == (m + 1) / 2 + l * 2 - 1 || c == (m + 1) / 2 + l * 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else {
                if ( c >= (m - 1) / 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
        }
    }

    if ( transposed ) {
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                aux[c][l] = mat[l][c];
        }
        swap( n, m );
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                mat[l][c] = (aux[l][c] == '+' ? '-' : '+');
        }
    }

    return eval( n, m );
}

int solve6( int n, int m ) {
    if ( n != 5 && m != 5 )
        return 0;
    
    bool transposed = false;
    if ( n != 5 ) {
        swap( n, m );
        transposed = true;
    }

    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l < 2 )
                mat[l][c] = '-';
            else if ( l == 2 ) {
                if ( c <= (m + 1) / 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else if ( l == 3 ) {
                if ( c < (m + 1) / 2 - 1 || c >= m - 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
            else if ( l == 4 ) {
                if ( c >= m / 2 - 1 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
        }
    }

    if ( transposed ) {
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                aux[c][l] = mat[l][c];
        }
        swap( n, m );
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                mat[l][c] = (aux[l][c] == '+' ? '-' : '+');
        }
    }
    
    return eval( n, m );
}


int solve7( int n, int m ) {
    bool transposed = false;
    if ( n > m ) {
        swap( n, m );
        transposed = true;
    }

    int specialLines = n - 2;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l >= specialLines )
                mat[l][c] = '-';
            else if ( l == 0 ) {
                if ( c < m / 2 + 1 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            } else if ( l <= specialLines / 2 ) {
                if ( c < (m + 1) / 2 - 1 || c == (m + 1) / 2 + l * 2 - 1 || c == (m + 1) / 2 + l * 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            } else {
                if ( c >= (m - 1) / 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
        }
    }

    if ( transposed ) {
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                aux[c][l] = mat[l][c];
        }
        swap( n, m );
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                mat[l][c] = (aux[l][c] == '+' ? '-' : '+');
        }
    }

    return eval( n, m );
}

int solve8( int n, int m ) {
    bool transposed = false;
    if ( n > m ) {
        swap( n, m );
        transposed = true;
    }

    int specialLines = n - 3;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( l >= specialLines )
                mat[l][c] = '-';
            else if ( l == 0 ) {
                if ( c < m / 2 + 1 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            } else if ( l <= specialLines / 2 ) {
                if ( c < (m + 1) / 2 - 1 || c == (m + 1) / 2 + l * 2 - 1 || c == (m + 1) / 2 + l * 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            } else {
                if ( c >= (m - 1) / 2 )
                    mat[l][c] = '+';
                else
                    mat[l][c] = '-';
            }
        }
    }

    if ( transposed ) {
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                aux[c][l] = mat[l][c];
        }
        swap( n, m );
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                mat[l][c] = (aux[l][c] == '+' ? '-' : '+');
        }
    }

    return eval( n, m );
}

int main() {
    int t;

    cin >> t;
    for ( ; t > 0; t-- ) {
        int n, m;

        cin >> n >> m;

        int best = 1, r = solve1( n, m );
        if ( solve2( n, m ) > r ) {
            best = 2;
            r = solve2( n, m );
        }
        if ( solve3( n, m ) > r ) {
            best = 3;
            r = solve3( n, m );
        }
        if ( solve4( n, m ) > r ) {
            best = 4;
            r = solve4( n, m );
        }
        if ( solve5( n, m ) > r ) {
            best = 5;
            r = solve5( n, m );
        }
        if ( solve6( n, m ) > r ) {
            best = 6;
            r = solve6( n, m );
        }
        if ( solve7( n, m ) > r ) {
            best = 7;
            r = solve7( n, m );
        }
        if ( solve8( n, m ) > r ) {
            best = 8;
            r = solve8( n, m );
        }

        if ( best == 1 )
            solve1( n, m );
        if ( best == 2 )
            solve2( n, m );
        if ( best == 3 )
            solve3( n, m );
        if ( best == 4 )
            solve4( n, m );
        if ( best == 5 )
            solve5( n, m );
        if ( best == 6 )
            solve6( n, m );
        if ( best == 7 )
            solve7( n, m );
        if ( best == 8 )
            solve8( n, m );

        cout << r << "\n";
        for ( int l = 0; l < n; l++ ) {
            for ( int c = 0; c < m; c++ )
                cout << mat[l][c];
            cout << "\n";
        }
    }

    return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31