Submission #1205417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205417		m5588ohammed	Paint By Numbers (IOI16_paint)	C++20	100 / 100	315 ms	59836 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool dp1[200001][101],vis[200001][101];
int siz[101],pre[200001][2],w[2000001],b[200001];
int n,k;
string s;
int sum(int l,int r,int u){
    return pre[r][u]-pre[l-1][u];
}
bool dfs1(int i,int gr){
    if(vis[i][gr]!=0) return dp1[i][gr];
    
    if(i==n+1){
        if(gr==k+1) return 1;
        return 0;
    }
    vis[i][gr]=1;
    if(s[i]=='X') return 0;

    if(i<=n){
        if(dfs1(i+1,gr)==1){
            dp1[i][gr]=1;
            w[i]++;
            w[i+1]--;
        }
    }

    if(i+siz[gr]<=n&&gr!=k+1&&sum(i+1,i+siz[gr],0)==0){
        if(dfs1(i+siz[gr]+1,gr+1)==1){
            dp1[i][gr]=1;
            w[i]++;
            w[i+1]--;
            b[i+1]++;
            b[i+siz[gr]+1]--;
        }
    }
    return dp1[i][gr];
}
string solve_puzzle(string t, vector<int> c) {
    s='#'+t;
    n=s.size()-1;k=c.size();
    for(int i=0;i<c.size();i++) siz[i+1]=c[i];
    for(int i=1;i<=n;i++){
        if(s[i]=='X') pre[i][1]++;
        if(s[i]=='_') pre[i][0]++;
        pre[i][0]+=pre[i-1][0];
        pre[i][1]+=pre[i-1][1];
    }
    if(sum(1,siz[1],0)==0&&dfs1(siz[1]+1,2)==1){
        b[1]++;
        b[siz[1]+1]--;    
    }
    dfs1(1,1);
    int sum1=0,sum2=0;
    string ans="";
    for(int i=1;i<=n;i++){
        sum1+=w[i];
        sum2+=b[i];
        if(sum1>0&&sum2>0) ans+='?';
        else if(sum1>0) ans+='_';
        else ans+='X';
    }
    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: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10