Submission #233017

#	Time	Username	Problem	Language	Result	Execution time	Memory
233017		aggu_01000101	Paint By Numbers (IOI16_paint)	C++14	59 / 100	5 ms	384 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;
int n, k;
vector<int> cc;
string str;
int sum[200005];
int prevb[200005];
int dp[200005][105];
bool white[200005];
int black[200005];
//Condition is if (i-1) started between (ind[i]-c[i-1]+1)
int f(int i, int j){
    //cout<<"f("<<i<<", "<<j<<") ";
    if(j>=k && i>n){
        return 1;
    }
    if(i>n){
        //cout<<i<<" "<<n<<" i has exceeded n"<<endl;
        return 0;
    }
    if(dp[i][j]!=-1){
        //cout<<i<<" "<<j<<" dp[i][j] is already defined as "<<dp[i][j]<<endl;
        return dp[i][j];
    }
    if(j>=k){
        if(str[i]=='X') return dp[i][j] = 0;
        int temp = f(i+1, j);
        if(temp==1) white[i-1] = true;
        return dp[i][j] = temp;
    }
    if(str[i-1]=='_'){
        //cout<<"This index can only be white"<<endl;
        int temp = f(i+1, j);
        if(temp>=1) white[i-1] = true;
        return dp[i][j] = temp;
    }
    if((i+cc[j]-1)>n){
        //cout<<i<<" "<<cc[j]<<" out of bounds"<<endl;
        return dp[i][j] = 0;
    }
    int ans = 0;
    if(((sum[i+cc[j]-1] - sum[i-1])==0) && ((i+cc[j]<=n)?(str[i+cc[j]-1]!='X'):true)) {
        int temp = f(i+cc[j]+1, j+1);
        if(temp>=1){
            black[i-1]++;
            black[i+cc[j]-1]--;
            white[i+cc[j]-1] = true;
            //cout<<"it's possible to place a block at "<<i<<endl;
        }
        ans+=temp;
        //cout<<"placing piece here "<<ans<<endl;
    }
    if(str[i-1]!='X'){
        int temp = f(i+1, j);
        if(temp>=1){
            white[i-1] = true;
        }
        ans+=temp;
    }
    if(ans>=1) ans = 1;
    //cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
    return dp[i][j] = ans;
}
string solve_puzzle(string s, vector<int> c){
    str = s;
    cc = c;
    k = c.size();
    n = s.length();
    s[0] = 0;
    for(int i = 0;i<n;i++){
        if(s[i]=='_'){
            sum[i+1]=1;
        }
        else sum[i+1] = 0;
        sum[i+1]+=sum[i];
        //cout<<(i+1)<<" "<<sum[i+1]<<endl;
    }
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=k;j++){
            dp[i][j] = -1;
        }
    }
    int ind = 0;
    for(int i = 1;i<=n;i++){
        prevb[i] = ind;
        if(s[i-1]=='X') ind = i;
    }
    for(int i = 0;i<=n;i++) white[i] = false;
    for(int i = 0;i<=n;i++) black[i] = 0;
    f(1, 0);
    string ans = s;
    for(int i = 0;i<n;i++) ans[i] = '?';
    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';
        //cout<<i<<" "<<black[i]<<" "<<white[i]<<endl;
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<k;j++){
            //cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
        }
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10