Submission #1306703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306703		enzy	Paint By Numbers (IOI16_paint)	C++20	100 / 100	470 ms	176080 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v.size())
const int maxn=2e5+10;
const int maxk=110;
int dpl[maxn][maxk], dpr[maxn][maxk], sp[maxn], v[maxn], tam[maxk], white[maxn], black[maxn];
int sum(int l, int r){
    if(l>r) swap(l,r);
    return sp[r]-sp[l-1];
}
void calc(int n, int k){
    memset(dpl,0,sizeof(dpl)); memset(dpl,0,sizeof(dpr));
    dpl[0][0]=1; // no 0 pego 0 caras
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){ // ja coloquei j caras
            if(!v[i+1]) dpl[i+1][j]|=dpl[i][j]; // posso deixar branco
            if(j!=k&&i+tam[j+1]<=n&&sum(i+1,i+tam[j+1])==0&&v[i+tam[j+1]+1]==0) dpl[i+tam[j+1]+1][j+1]|=dpl[i][j];
        }
    }
    dpr[n+1][k+1]=1;
    for(int i=n+1;i>1;i--){
        for(int j=k+1;j>=1;j--){
            if(!v[i-1]) dpr[i-1][j]|=dpr[i][j];
            if(j!=1&&i-tam[j-1]>=1&&sum(i-tam[j-1],i-1)==0&&v[i-tam[j-1]-1]==0) dpr[i-tam[j-1]-1][j-1]|=dpr[i][j];
        }
    }
}
string solve_puzzle(string s, vector<int> c){
    int n=s.size(), k=c.size();
    s='a'+s; // 1 indexed
    for(int i=1;i<=k;i++) tam[i]=c[i-1];
    for(int i=1;i<=n;i++){
        sp[i]=sp[i-1];
        if(s[i]=='X') v[i]=1;
        if(s[i]=='_') sp[i]++;
    }
    calc(n,k);
    memset(white,0,sizeof(white)); memset(black,0,sizeof(black));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k+1;j++) if(dpl[i][j-1]&&dpr[i][j]) white[i]++; // checando se pode ser branco
    }
    for(int j=1;j<=k;j++){
        for(int i=1;i+tam[j]-1<=n;i++){
            // vou brutar se o j-esimo intervalo estiver em [i,i+tam[j]-1], ainda eh possivel completar o resto?
            if(sum(i,i+tam[j]-1)==0&&dpl[i-1][j-1]&&dpr[i+tam[j]][j+1]) black[i]++, black[i+tam[j]]--;
        }
    }
    string ret="";
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=black[i];
        if(s[i]!='.') ret.push_back(s[i]);
        else{
            if(sum&&white[i]) ret.push_back('?');
            else if(sum) ret.push_back('X');
            else ret.push_back('_');
        }
    }
    return ret;
}

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