Submission #607571

#	Time	Username	Problem	Language	Result	Execution time	Memory
607571		APROHACK	Paint By Numbers (IOI16_paint)	C++14	90 / 100	10 ms	6484 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ll long long
using namespace std;

ll k, n;
string str;
bool white[6000][2];
int mem[5005][105];
vector<int>cs;
bool dp(int position, int ci ){
    if(ci==k && position == n)return true;
    if(position >= n)return false;
    if(mem[position][ci] != -1)return mem[position][ci];
    //cout << " anali" << position <<  " " << ci << endl;
    if(str[position]=='_'){
        white[position][0]=true;
        //cout << position << " " << ci << " " << dp(position+1, ci) << endl;
        return mem[position][ci] = dp(position+1, ci);
    }else if(str[position] != 'X'){ // .
        bool ret = false;
        if(dp(position+1, ci)){
            white[position][0]=true;
            ret = true;
        }
        bool posible = true;
        if(ci==k){
            //cout << position << " " << ci << " " << ret << endl;
            return mem[position][ci] = ret ;
        }
        for(int i = position+1 ; i < position + cs[ci] ; i++){
            if(i==n){
                posible = false;
                break;
            }
            if(str[i]=='_')posible = false;
        }
        if(position+cs[ci] > n || str[position+cs[ci]] == 'X')posible = false;
        if(posible && ((position+cs[ci] == n && ci == k-1) || dp(position+cs[ci]+1, ci+1))){
            white[position][1]=true;
            white[position+cs[ci]][0]=true;
            for(int i = position+1 ; i < position +cs[ci] ; i++)white[i][1]=true;
            //cout<< " nice "<< position << endl;
            return mem[position][ci] = true;
        }
        //cout << position << " " << ci << " " << ret << endl;
        return mem[position][ci] = ret ;        
    }else{
        if(ci == k)return false;
        bool posible = true;
        for(int i = position+1 ; i < position + cs[ci] ; i++){
            if(i==n)return false;
            if(str[i]=='_'){
                //cout << position << " " << ci << " " << false << endl;
                return mem[position][ci] = false;
            }
        }
        if(position+cs[ci] > n || str[position+cs[ci]] == 'X')posible = false;
        if(posible && ((position+cs[ci] == n  && ci == k-1)||dp(position+cs[ci]+1, ci+1))){
            white[position][1]=true;
            white[position+cs[ci]][0]=true;
            for(int i = position+1 ; i < position +cs[ci] ; i++)white[i][1]=true;
            //cout << position << " " << ci << " " << true << endl;
            return mem[position][ci] =true;
        }
        //cout << position << " " << ci << " " << false << endl;
        return mem[position][ci] =false;
    }
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    k=c.size(), n = s.size();
    str = s;
    for(int i = 0 ; i < k ; i ++)cs.pb(c[i]);
    memset(white, false, sizeof white);
    memset(mem, -1, sizeof mem);
    dp(0, 0);
    string ans = "";
    for(int i = 0 ; i < n ; i++){
        if(white[i][0] && white[i][1])ans+="?";
        else if(white[i][0] )ans+="_";
        else ans+= "X";
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool dp(int, int)':
paint.cpp:22:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |         return mem[position][ci] = dp(position+1, ci);
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:32:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   32 |             return mem[position][ci] = ret ;
      |                    ~~~~~~~~~~~~~~~~~~^~~~~
paint.cpp:47:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   47 |             return mem[position][ci] = true;
      |                    ~~~~~~~~~~~~~~~~~~^~~~~~
paint.cpp:50:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   50 |         return mem[position][ci] = ret ;
      |                ~~~~~~~~~~~~~~~~~~^~~~~
paint.cpp:58:42: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   58 |                 return mem[position][ci] = false;
      |                        ~~~~~~~~~~~~~~~~~~^~~~~~~
paint.cpp:67:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 |             return mem[position][ci] =true;
      |                    ~~~~~~~~~~~~~~~~~~^~~~~
paint.cpp:70:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   70 |         return mem[position][ci] =false;
      |                ~~~~~~~~~~~~~~~~~~^~~~~~

• 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: 0 / 10