Submission #1289930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289930		Rares	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	580 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/

const int MAXK=205;
const int MAXN=200010;

int dp[MAXK][MAXN],n,k,fr[2][MAXN],a[MAXN];
int mars[MAXN],nmars[MAXN];
string rez;

string solve_puzzle (string s, vector <int> c){
    n=s.size ();
    k=c.size ();

    for (int i=0;i<n;++i){
        if (s[i]=='.') a[i+1]=2;
        if (s[i]=='_') a[i+1]=1;
        if (s[i]=='X') a[i+1]=0;
    }
    fr[0][n+1]=fr[1][n+1]=n+1;
    for (int i=n;i>=1;--i){
        fr[0][i]=fr[0][i+1];
        fr[1][i]=fr[1][i+1];
        if (a[i]<2) fr[a[i]][i]=i;
    }
    a[n+1]=2;
    a[0]=2;
    mars[1]=1;
    mars[fr[0][1]+1]=-1;
    int fp=1,nfp;
    for (int i=0;i<k;++i){
        nfp=n+1;
        for (int j=1;j<=n;++j){
            mars[j]+=mars[j-1];
        }
        for (int j=fp;j<=n-c[i]+1;++j){
            ///pot pune blocul i pe pozitia j?

            if (fr[1][j]<=j+c[i]-1) continue;
            if (a[j+c[i]]==0 or a[j-1]==0) continue;
            if (mars[j]==0) continue;
            nmars[j+c[i]+1]++;
            nmars[fr[0][j+c[i]]+1]--;
            dp[i][j]=1;
            nfp=min (nfp,j+c[i]+1);

        }

        for (int j=1;j<=n;++j){
            mars[j]=nmars[j];
            nmars[j]=0;
        }
        fp=nfp;
    }
    for (int i=0;i<=n+1;++i) mars[i]=0;
    fp=n;



    for (int i=k-1;i>=0;--i){
        nfp=0;
        for (int j=fp;j>=1;--j){
            if (i==k-1 and fr[0][j]!=n+1 and fr[0][j]>=j+c[i]) break;
            if (dp[i][j]==1){
                if (i)
                    nfp=max (nfp,j-1-c[i-1]);
                dp[i][j]=2;
            }
        }

        fp=nfp;
    }
    for (int i=0;i<n;++i){
        if (s[i]=='.') rez.push_back ('?');
        else rez.push_back (s[i]);
    }
    for (int i=0;i<=k-1;++i){
        int l=n+1,r=0;
        for (int j=1;j<=n;++j){
            if (dp[i][j]==2){
                l=min (l,j);
                r=max (r,j);
                mars[j]++;
                mars[j+c[i]]--;

            }
        }

        for (int j=r;j<=l+c[i]-1;++j){
            rez[j-1]='X';
        }
    }

    for (int i=1;i<=n;++i){
        mars[i]+=mars[i-1];
        if (mars[i]==0) rez[i-1]='_';
    }


    return rez;
}

/**int main()
{
    string s;
    cin >>s;
    vector <int> c;
    int x;
    while (fin >>x){
        c.push_back (x);
    }
    cout <<solve_puzzle (s,c);
    return 0;
}**/

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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10