제출 #1289939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289939		Rares	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	592 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],fl[2][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;
    }


    fl[0][0]=fl[1][0]=-1;
    for (int i=1;i<=n;++i){
        fl[0][i]=fl[0][i-1];
        fl[1][i]=fl[1][i-1];
        if (a[i]<2) fl[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;


    mars[n]=1;
    if (fl[0][n]-c[k-1]>=0) mars[fl[0][n]-c[k-1]]--;
    for (int i=k-1;i>=0;--i){
        nfp=0;

        for (int i=n;i>=1;--i){
            mars[i]+=mars[i+1];
        }


        for (int j=fp;j>=1;--j){

            if (dp[i][j]==1 and mars[j]>0){
                if (i){
                    nfp=max (nfp,j-1-c[i-1]);
                    if (j-1-c[i-1]>=0)
                        nmars[j-1-c[i-1]]++;
                    if (fl[0][j-1]-c[i-1]>=0) nmars[fl[0][j-1]-c[i-1]]--;
                }

                dp[i][j]=2;

            }
        }
        for (int j=n;j>=1;--j){
            mars[j]=nmars[j];
            nmars[j]=0;
        }

        fp=nfp;
    }



    for (int j=0;j<=n+1;++j) mars[j]=0;
    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;
}**/

컴파일 시 표준 에러 (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