Submission #607601

#	Time	Username	Problem	Language	Result	Execution time	Memory
607601		APROHACK	Paint By Numbers (IOI16_paint)	C++14	100 / 100	521 ms	182008 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[200005][2];
ll prefixed [200005], cuenta[200005];
ll mem[200005][105];
vector<ll>cs;
void llenar(ll dd, ll ht){
    prefixed[dd]+=1;
    prefixed[ht+1]+=-1;
}
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 ;
        }
        if(position+cs[ci]-1>=n)posible = false;
        if(cuenta[position+cs[ci]-1] != cuenta[position])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;
            llenar(position+1, position+cs[ci]-1);
            //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;
        if(position+cs[ci]-1>=n)return mem[position][ci] = false;
        if(cuenta[position+cs[ci]-1] != cuenta[position])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;
            llenar(position+1, position+cs[ci]-1);
            //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);
    ll cur = 0;
    for(int i = 0 ; i  < n ; i++){
        if(str[i]=='_')cuenta[i]=++cur;
        else cuenta[i]=cur;
    }
    for(int i = 0 ; i  < n ; i ++)//cout << cuenta [i] << " ";
    //cout << endl;
    dp(0, 0);
    string ans = "";
    int pre = 0;
    for(int i = 0 ; i < n ; i++){
        pre+=prefixed[i];
        //cout<<prefixed[i] << " ";
        if(white[i][0] && (white[i][1] || pre > 0))ans+="?";
        else if(white[i][0] )ans+="_";
        else ans+= "X";
    }
    //cout << endl;
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool dp(int, int)':
paint.cpp:27:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |         return mem[position][ci] = dp(position+1, ci);
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:37:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |             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:54:58: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   54 |         if(position+cs[ci]-1>=n)return mem[position][ci] = false;
      |                                        ~~~~~~~~~~~~~~~~~~^~~~~~~
paint.cpp:55:83: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   55 |         if(cuenta[position+cs[ci]-1] != cuenta[position])return mem[position][ci] = false;
      |                                                                 ~~~~~~~~~~~~~~~~~~^~~~~~~
paint.cpp:62:38: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |             return mem[position][ci] =true;
      |                    ~~~~~~~~~~~~~~~~~~^~~~~
paint.cpp:65:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   65 |         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: 10 / 10