Submission #32063

#	Time	Username	Problem	Language	Result	Execution time	Memory
32063		osmanorhan	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1503 ms	55000 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )

using namespace std;

typedef long long Lint;
typedef pair<int,int> ii;

const int maxn = 200020;

int a, k;
string s;
vector<int> c;
int c0[maxn], c1[maxn];
int sum[maxn];
bool dn[maxn][102];
bool used[maxn][102];

bool f( int n, int r ) {
    if( n == a+1 ) {
        if( r == k ) return true;
        return false;
    }
    if( used[n][r] ) return dn[n][r];
    used[n][r] = 1;
    bool &ret = dn[n][r];
    ret = false;

    if( s[n] != 'X' ) {
        if( f( n+1, r ) ) c0[n] = 1, ret = true;
    }
    if( r < c.size() && n+c[r] <= a ) {
        if( sum[n-1] == sum[ n+c[r]-1 ] && s[ n+c[r] ] != 'X' ) {
            if( f( n+c[r]+1, r+1 ) ) {
                c0[ n+c[r] ] = 1;
                c1[ n ]++;
                c1[ n+c[r] ]--;
                ret = 1;
            }
        }
    }

    return ret;
}

string solve_puzzle(string S, vector<int> C) {
    s = S;
    c = C;
    a = s.size();
    k = c.size();

    string ans = "";

    s += '_';

    for(int i=0;i<s.size();i++)
        sum[i] = (s[i]=='_') + (i? sum[i-1]:0);

    f( 0, 0 );
    for(int i=0,k=0;i<a;i++) {
        k += c1[i];
        if( k && c0[i] ) ans += '?';
        else if( !k && c0[i] ) ans += '_';
        else if( k && !c0[i] ) ans += 'X';
        else assert(0);
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool f(int, int)':
paint.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if( r < c.size() && n+c[r] <= a ) {
           ^
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++)
                  ^

• 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