Submission #367190

#	Time	Username	Problem	Language	Result	Execution time	Memory
367190		uacoder123	Paint By Numbers (IOI16_paint)	C++14	100 / 100	419 ms	163556 KiB

paint

    #include "paint.h"
        #include <bits/stdc++.h>
        #include <ext/pb_ds/assoc_container.hpp>
        using namespace std;
        using namespace __gnu_pbds;
        #define F first
        #define S second
        #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
        #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
        #define all(x) (x).begin(), (x).end()
        #define sz(x) lli(x.size())
        #define mp(i,a) make_pair(i,a)
        #define pb(a) push_back(a)
        #define bit(x,b) (x&(1LL<<b))
        typedef long long int lli;
        typedef pair <lli,lli> ii;
        typedef pair <ii,lli> iii;
        typedef vector <lli> vi;
        int dp[2*100010][103],dp1[2*100010][103],pw[2*100010];
        std::string solve_puzzle(std::string s, std::vector<int> c) 
        {
            c.pb(0);
            c.insert(c.begin(),0);
            string s1=s;
            s="  "+s;
            int n=s.size()-2,k=c.size();
            for(int i=0;i<n;++i)
                s1[i]='?';
            for(int i=2;i<=n+1;++i)
            {
                pw[i]=pw[i-1];
                if(s[i]=='_')
                    pw[i]++;
            }
            for(int i=0;i<k;++i)
            {
                if(i==k-1)
                    dp[n+3][i]=1;
                else
                    dp[n+3][i]=0;
                if(i==k-1)
                    dp[n+2][i]=1;
                else
                    dp[n+2][i]=0;
                if(i==0)
                    dp1[0][i]=1;
                else
                    dp1[0][i]=0;
                if(i==0)
                    dp1[1][i]=1;
                else
                    dp1[1][i]=0;
            }
            for(int i=n+1;i>=2;--i)
            {
                for(int j=k-1;j>=0;--j)
                {
                    if(j==0)
                    {
                        dp[i][j]=dp[i][j+1];
                        continue;
                    }
                    if(s[i]!='X')
                        dp[i][j]=dp[i+1][j];
                    if(s[i]!='_'&&c[j]>0)
                    {
                        if(i+c[j]-1<=n+1&&pw[i+c[j]-1]-pw[i-1]==0&&(i+c[j]>n+1||s[i+c[j]]!='X'))
                            dp[i][j]=max(dp[i][j],dp[i+c[j]+1][j+1]);
                    }
                }
            }
            for(int i=2;i<=n+1;++i)
            {
                for(int j=0;j<k;++j)
                {
                    if(j==k-1)
                    {
                        dp1[i][j]=dp1[i][j-1];
                        continue;
                    }
                    if(s[i]!='X')
                        dp1[i][j]=dp1[i-1][j];
                    if(s[i]!='_'&&c[j]>0)
                    {
                        if(i-(c[j]-1)>=2&&pw[i]-pw[i-(c[j]-1)-1]==0&&(i-(c[j]-1)-1<2||s[i-(c[j]-1)-1]!='X'))
                            dp1[i][j]=max(dp1[i][j],dp1[i-(c[j]-1)-2][j-1]);
                    }
                }
            }
            int re=0;
            for(int i=2;i<=n+1;++i)
            {
                int fl=0,fl1=0;
                for(int j=1;j<k;++j)
                {
                    if(s[i]!='X'&&dp[i+1][j]+dp1[i-1][j-1]==2)
                        fl=1;
                    int in=i+c[j]-1;
                    if(s[i]!='_'&&j!=k-1&&in<=n+1&&pw[in]-pw[i-1]==0&&s[i-1]!='X'&&(in+1>n+1||s[in+1]!='X'))
                    {
                        if(dp1[i-2][j-1]+dp[in+2][j+1]==2)
                        {
                            fl1=1;
                            re=max(re,c[j]);
                        }
                    }
                }
                if(re>0)
                {
                    fl1=1;
                    re--;
                }
                if(fl+fl1==2)
                    continue;
              if(fl+fl1==0)
                exit(1);
                if(fl)
                    s1[i-2]='_';
                else
                    s1[i-2]='X';
         
            }
            return s1;
        }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:115:15: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  115 |               if(fl+fl1==0)
      |               ^~
paint.cpp:117:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  117 |                 if(fl)
      |                 ^~

• 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