Submission #479747

#	Time	Username	Problem	Language	Result	Execution time	Memory
479747		Dan4Life	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2079 ms	260888 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;
string ans, ss;
vector<int> C;
int pref[200010], pref2[200010], a[200010][2];
int dp[200010][101][3];

bool recur(int pos, int num, bool ok=false)
{
    if(dp[pos][num][ok]!=-1) return dp[pos][num][ok];
    if(pos==n) return dp[pos][num][ok]=(num==k and !ok);
    bool op1=false, op2=false;
    if(num==k){
        int cnt = pref2[n]-pref2[pos];
        if(cnt) return false;
        op2 = recur(pos+1, num, false);
        if(op2) a[pos][0] = 1;
        return dp[pos][num][ok]=true;
    }
    int cnt = C.at(num);
    if(ss[pos]=='_' or ok)
    {
        if(ss[pos]=='X') return dp[pos][num][ok]=false;
        op2 = recur(pos+1, num, false);
    }
    else if(ss[pos]=='X'){
        if(pos+cnt<=n and pref[pos+cnt]==pref[pos])
            op1 = recur(pos+cnt, num+1, num!=k-1);
    }
    else{
        if(pos+cnt<=n and pref[pos+cnt]==pref[pos])
            op1 = recur(pos+cnt, num+1, num!=k-1);
        op2 = recur(pos+1, num);
    }
    if(op1) a[pos][1]++, a[pos+cnt][1]--;
    if(op2) a[pos][0] = 1;
    return dp[pos][num][ok]=(op1||op2);
}

string solve_puzzle(string s, vector<int> c)
{
    n = (int)s.size(), k = (int)c.size();
    ss = s, C = c, pref[0]=pref2[0]=0;
    for(int i = 0; i < n; i++)
        pref[i+1] = pref[i]+(s[i]=='_'?1:0),
        pref2[i+1] = pref2[i]+(s[i]=='X'?1:0);
    memset(dp, -1, sizeof(dp)), recur(0, 0);
    for(int i = 0; i < n; i++)
    {
        a[i+1][1]+=a[i][1];
        if(a[i][1] and a[i][0]) ans+='?';
        else if(a[i][1]) ans+='X';
        else ans+='_';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool recur(int, int, bool)':
paint.cpp:14:39: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   14 |     if(pos==n) return dp[pos][num][ok]=(num==k and !ok);
      |                       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
paint.cpp:21:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |         return dp[pos][num][ok]=true;
      |                ~~~~~~~~~~~~~~~~^~~~~
paint.cpp:26:49: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   26 |         if(ss[pos]=='X') return dp[pos][num][ok]=false;
      |                                 ~~~~~~~~~~~~~~~~^~~~~~
paint.cpp:40:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |     return dp[pos][num][ok]=(op1||op2);
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~

• 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