Submission #566575

#	Time	Username	Problem	Language	Result	Execution time	Memory
566575		n0sk1ll	Paint By Numbers (IOI16_paint)	C++14	0 / 100	1 ms	212 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;
long long int typedef li;

bool dp[103][103];
int gdemin[103][103];
int gdemax[103][103];

bool moze(int l, int r, string &s)
{
    for (int i=l-1;i<=r-1;i++) if (s[i]=='_') return false;
}

string smin,smax;

void rekurzmin(int n, int k, vector<int> &c)
{
    if (n<=0) return;
    for (int i=n-c[k-1]+1;i<=n;i++) smin[i-1]='X';
    rekurzmin(gdemin[n][k],k-1,c);
}

void rekurzmax(int n, int k, vector<int> &c)
{
    if (n<=0) return;
    for (int i=n-c[k-1]+1;i<=n;i++) smax[i-1]='X';
    rekurzmax(gdemax[n][k],k-1,c);
}

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

    for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) gdemin[i][j]=-69,gdemax[i][j]=-69;

    for (int i=c[0];i<=n;i++) if (moze(i-c[0]+1,i,s)) dp[i][1]=1;

    for (int j=2;j<=k;j++)
        for (int i=c[j-1];i<=n;i++)
            for (int xd=-1;xd<=i-(c[j-1]+1);xd++)
                if (dp[xd][j-1] && moze(xd+2,xd+c[j-1]+1,s)){
                    dp[i][j]=1;
                    gdemax[i][j]=xd;
                    if (gdemin[i][j]==-69) gdemin[i][j]=xd;
                }

    /*for (int j=1;j<=k;j++)
    {
        for (int i=1;i<=n;i++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/

    for (int i=1;i<=n;i++) smin.push_back('_'),smax.push_back('_');

    for (int i=1;i<=n;i++) if (dp[i][k])
    {
        rekurzmin(i,k,c);
        break;
    }

    for (int i=n;i>=1;i--) if (dp[i][k])
    {
        rekurzmax(i,k,c);
        break;
    }

    //cout<<smin<<endl<<smax<<endl;

    string ans;
    for (int i=0;i<n;i++) if (smin[i]==smax[i]) ans.push_back(smin[i]); else ans.push_back('?');

    return ans;
}

/*

..........
2 3 4

*/

Compilation message (stderr)

paint.cpp: In function 'bool moze(int, int, std::string&)':
paint.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
   15 | }
      | ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10