Submission #1197559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197559		YassirSalama	Paint By Numbers (IOI16_paint)	C++20	7 / 100	1 ms	1096 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#ifdef IOI
template<typename T> 
void dbg(const T& t){
    cout<<t<<endl;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
    cout<<t<<" , ";
    dbg(args...);
}
#define dbg(...) cout<<'('<<#__VA_ARGS__<<") : ";dbg(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
string s;
vector<int> c;
int n,k;
const int maxn = 2e5+100;
int dp[maxn][101][2];// 0 being black
int dp2[maxn][101][2];
int pref[maxn];
int sum(int l,int r){
    return pref[r]-pref[l];
}
string solve_puzzle(string ss, vector<int> cc) {s=ss;c=cc;n = s.length();k = c.size();
    memset(pref,0,sizeof(pref));
    for(int i  =0;i<n;i++){
        pref[i+1] = pref[i];
        pref[i+1] += (s[i]=='_');
    }
    dp[0][0][0]=1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<=k;j++){
            if(s[i]!='X'){
                dp[i+1][j][0]|=dp[i][j][0];
                dp[i+1][j][0]|=dp[i][j][1];
            }
            if(j+1<=k&&i+c[i]<=n&&sum(i,i+c[j])==0)
                dp[i+c[j]][j+1][1]|=(dp[i][j][0]);
        }
    }
    #define all(s) s.begin(),s.end()
    reverse(all(s));
    memset(pref,0,sizeof(pref));
    for(int i = 0;i<n;i++){
        pref[i+1]=pref[i];
        pref[i+1] += (s[i]=='_');
    }
    dp2[0][0][0]=1;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<=k;j++){
            if(s[i]!='X'){
                dp2[i+1][j][0]|=dp2[i][j][0];
                dp2[i+1][j][0]|=dp2[i][j][1];
            }
            if(j+1<=k&&i+c[k-j-1]<=n&&sum(i,i+c[k-1-j])==0)
                dp2[i+c[k-1-j]][j+1][1]|=(dp2[i][j][0]);
        }
    }
    string ans(n,'?');
    int mx = 0;
    auto f = [&](int i){
        return n-i+1;
    };
    for(int i=1;i<=n;i++){
        bool w = 0;
        bool b = 0;
        for(int j=0;j<=k;j++){
            w|=(dp[i][j][0]&dp2[f(i)][k-j][0]);
            if(j+1<=k&&dp[i-1][j][0]&&dp2[f(i)][k-j][1]){
                mx = max(mx,i+c[j]);
            }
        }
        b|=(i<mx);
        if(!b&&w){
            ans[i-1] = '_';
            continue;
        }
        if(!w&&b){
            ans[i-1]='X';
            continue;
        }
        ans[i-1]='?';
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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