Submission #1162562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162562		AlgorithmWarrior	Paint By Numbers (IOI16_paint)	C++20	100 / 100	432 ms	125344 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

int const MAXN=2e5+5;
int const MAXK=105;

int lines[MAXN];
bool okpref[MAXN][MAXK];
bool oksuf[MAXN][MAXK];
int okX[MAXN][MAXK];

bool canbe_(char ch){
    return ch=='_' || ch=='.';
}

bool canbeX(char ch){
    return ch=='X' || ch=='.';
}

string solve_puzzle(string s,vector<int>c) {
    int i,j;
    int n=s.size();
    int k=c.size();
    for(i=1;i<=n;++i){
        if(s[i-1]=='_')
            lines[i]=1;
        lines[i]+=lines[i-1];
    }
    okpref[0][0]=1;
    for(i=1;i<=n;++i){
        okpref[i][0]=(okpref[i-1][0] && canbe_(s[i-1]));
        for(j=1;j<=k;++j){
            bool condition1=(canbe_(s[i-1]) && okpref[i-1][j]);
            bool condition2=0;
            if(i>=c[j-1])
                condition2=(lines[i]==lines[i-c[j-1]] && ((i-c[j-1]==0)?(j==1):(canbe_(s[i-c[j-1]-1]) && okpref[i-c[j-1]-1][j-1])));
            okpref[i][j]=(condition1 || condition2);
        }
    }
    oksuf[n+1][k+1]=1;
    for(i=n;i;--i){
        oksuf[i][k+1]=(oksuf[i+1][k+1] && canbe_(s[i-1]));
        for(j=1;j<=k;++j){
            bool condition1=(canbe_(s[i-1]) && oksuf[i+1][j]);
            bool condition2=0;
            if(i+c[j-1]-1<=n)
                condition2=(lines[i+c[j-1]-1]==lines[i-1] && ((i+c[j-1]-1==n)?(j==k):(canbe_(s[i+c[j-1]-1]) && oksuf[i+c[j-1]+1][j+1])));
            oksuf[i][j]=(condition1 || condition2);
        }
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=k;++j)
            if(i>=c[j-1])
                okX[i][j]=(lines[i]==lines[i-c[j-1]] && ((i-c[j-1]==0)?(j==1):(canbe_(s[i-c[j-1]-1]) && okpref[i-c[j-1]-1][j-1])) && ((i==n)?(j==k):(canbe_(s[i]) && oksuf[i+2][j+1])));
    for(j=1;j<=k;++j)
        for(i=1;i<=n;++i)
            okX[i][j]+=okX[i-1][j];
    string rasp;
    for(i=0;i<n;++i){
        if(s[i]!='.'){
            rasp.push_back(s[i]);
            continue;
        }
        bool hasSol_=0;
        for(j=0;j<=k;++j)
            hasSol_|=(okpref[i][j] && oksuf[i+2][j+1]);
        bool hasSolX=0;
        for(j=1;j<=k;++j){
            int last=min(i+c[j-1],n);
            hasSolX|=(okX[last][j]!=okX[i][j]);
        }
        if(hasSol_ && hasSolX)
            rasp.push_back('?');
        else
            if(hasSol_)
                rasp.push_back('_');
            else
                rasp.push_back('X');
    }
    return rasp;
}

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