oj.uz

Submission #566575

# Submission time Handle Problem Language Result Execution time Memory
566575 2022-05-22T12:28:06 Z n0sk1ll Paint By Numbers (IOI16_paint) C++14
0 / 100
 1 ms 212 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB char #0 differ - expected: '?', found: '_'
2 Halted 0 ms 0 KB -