Submission #233023

#	Time	Username	Problem	Language	Result	Execution time	Memory
233023		aggu_01000101	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1022 ms	101172 KiB

paint

#include <bits/stdc++.h>
#define INF 10000000000000000
#define MOD 1000000017
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
using namespace std;
const int N = 200005;
const int K = 105;
int n, k, temp;
vector<int> cc;
string str;
int sum[N], dp[N][K], black[N];
bool white[N];
int f(int i, int j){
    if(i>n) return (j>=k)?1:0;
    if(dp[i][j]!=-1) return dp[i][j];
    if(j>=k){
        if(str[i-1]=='X') return dp[i][j] = 0;
        if(f(i+1, j)==1){
            white[i-1] = true;
            return dp[i][j] = 1;
        }
        return dp[i][j] = 0;
    }
    if(str[i-1]=='_'){
        if(f(i+1, j)>=1){
            white[i-1] = true;
            return dp[i][j] = 1;
        }
        return dp[i][j] = 0;
    }
    if((i+cc[j]-1)>n){
        return dp[i][j] = 0;
    }
    int ans = 0;
    int whiteinrange = (sum[i+cc[j]-1] - sum[i-1]);
    if((whiteinrange==0) && (((i+cc[j]-1)>=n)||(str[i+cc[j]-1]!='X'))) {
        if(f(i+cc[j]+1, j+1)>=1){
            black[i-1]++;
            black[i+cc[j]-1]--;
            white[i+cc[j]-1] = true;
            ans = 1;
        }
    }
    if(str[i-1]!='X'){
        if(f(i+1, j)>=1){
            white[i-1] = true;
            ans = 1;
        }
    }
    return dp[i][j] = ans;
}
string solve_puzzle(string s, vector<int> c){
    str = s;
    cc = c;
    k = c.size();
    n = s.length();
    string ans = s;
    sum[0] = 0;
    for(int i = 0;i<n;i++) sum[i+1] = (s[i]=='_') + sum[i];
    for(int i = 0;i<n;i++){
        white[i] = black[i] = 0;
        ans[i] = '?';
        for(int j = 0;j<=k;j++){
            dp[i][j] = dp[i+1][j] = -1;
        }
    }
    f(1, 0);
    for(int i = 1;i<n;i++) black[i]+=black[i-1];
    for(int i = 0;i<n;i++){
        if(black[i]==0) ans[i] = '_';
        if(white[i]==false) ans[i] = 'X';
    }
    return ans;
}
/*int main(){
    string s;
    int kk;
    vector<int> c;
    cin>>s>>kk;
    for(int i = 0;i<kk;i++){
        int temp;
        cin>>temp;
        c.push_back(temp);
    }
    cout<<solve_puzzle(s, c)<<endl;
}*/

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:63:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
         white[i] = black[i] = 0;
                    ~~~~~~~~~^~~

• 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