Submission #1204348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204348		notme	Paint By Numbers (IOI16_paint)	C++20	90 / 100	2092 ms	8468 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005, maxk = 205;
int n, k;
int dp[maxn][maxk], suff[maxn][maxk];
int be1[maxn], be0[maxn];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
    n = s.size();
    k = c.size();
//cout << n << endl;
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < k; ++ j)
        {
            //cout << "solving " << i << " " << j << endl;
            if(i < n-1 && s[i+1] == 'X')
            {
                continue;
            }
            int len = c[j];
            int endpoint = i - len + 1;

            if(endpoint < 0)
            {
               // cout << "endpoint opa " << endl;
                continue;
            }

            int checkfree = 1;
            for (int index = i; index >= endpoint; -- index)
                if(s[index] == '_')checkfree = 0;
            if(!checkfree)
                continue;

            if(endpoint == 0 && j == 0)
            {
                dp[i][j] = 1;
                continue;
            }
            else if(endpoint == 0)continue;

            if(j == 0)
            {
                int ok = 1;
                for (int index = endpoint - 1; index >= 0; -- index)
                    if(s[index] == 'X')ok = 0;
                if(ok)dp[i][j] = 1;
              //  cout << "first did not pass?" << " " << ok << endl;
                continue;
            }
            checkfree = 1;
            if(s[endpoint-1] == 'X')checkfree = 0;
            int found = 0;
            for (int index = endpoint - 2; index >= 0; -- index)
            {
                if(checkfree == 0)break;
                if(dp[index][j-1])
                {
                    found = 1;
                    break;
                }
                if(s[index] == 'X')checkfree = 0;
                if(checkfree == 0)break;
            }
            if(found)dp[i][j] = 1;
           // else cout << "not found pre" << endl;
        }
    }
    /*cout << "dp " << endl;
    for (int i = 0; i < n; ++ i)
    {
        cout << i << ": ";
        for (int j = 0; j < k; ++ j)
            cout << dp[i][j] << " ";
        cout << endl;
    }*/
    for (int i = n-1; i >= 0; -- i)
    {
        for (int j = k-1; j >= 0; -- j)
        {
            if(i > 0 && s[i-1] == 'X')
            {
                continue;
            }
            int len = c[j];
            int endpoint = i + len - 1;
            if(endpoint > n - 1)continue;

            int checkfree = 1;
            for (int index = i; index <= endpoint; ++ index)
                if(s[index] == '_')checkfree = 0;
            if(!checkfree)continue;

            if(endpoint == n-1 && j == k-1)
            {
                suff[i][j] = 1;
                continue;
            }
            else if(endpoint == n-1)continue;

            if(j == k-1)
            {
                int ok = 1;
                for (int index = endpoint + 1; index <= n - 1; ++ index)
                    if(s[index] == 'X')ok = 0;
                if(ok)suff[i][j] = 1;
                continue;
            }
            checkfree = 1;
            if(s[endpoint+1] == 'X')checkfree = 0;
            int found = 0;
            for (int index = endpoint + 2; index < n; ++ index)
            {
                if(checkfree == 0)break;
                if(suff[index][j+1])
                {
                    found = 1;
                    break;
                }
                if(s[index] == 'X')checkfree = 0;
                if(checkfree == 0)break;
            }
            if(found)suff[i][j] = 1;
        }
    }
  /*  cout << "suff " << endl;
     for (int i = 0; i < n; ++ i)
    {
        cout << i << ": ";
        for (int j = 0; j < k; ++ j)
            cout << suff[i][j] << " ";
        cout << endl;
    }
    cout << "builing dp ended " << endl;*/
    for (int j = 0; j < k; ++ j)
    {
        int len = c[j];
        for (int start = 0; start < n; ++ start)
        {
          //  cout << "try " << start << " " << j << endl;
            int si = start;
            int fi = start + len - 1;
            if(fi >= n)
            {
               // cout << "out of range" << endl;
                continue;
            }
            int clean = 1;
            for (int index = si; index <= fi; ++ index)
                if(s[index] == '_')clean = 0;
            if(!clean)
            {
              //  cout << "range not clean" << endl;
                continue;
            }
            int cleanbef = si;
            for (int i = si-1; i >= 0; -- i)
            {

                if(s[i] == 'X')break;
                cleanbef = i;
            }
            int cleanaft = fi;
            for (int i = fi+1; i < n; ++ i)
            {
                if(s[i] == 'X')break;
                cleanaft = i;
            }
            int pre = -1;
            for (int i = start - 2; i >= 0; -- i)
            {
                if(i+1 < cleanbef)break;
                if(j - 1 >= 0 && dp[i][j-1])
                {
                    pre = i;
                   // break;
                }
            }
            if(pre == -1 && j != 0)
            {
               // cout << "error 1" << endl;
                continue;
            }

            int presuff = n;
            for (int i = fi + 2; i < n; ++ i)
            {
                if(i - 1 > cleanaft)break;
                if(j + 1 < n && suff[i][j+1])
                {
                    presuff = i;
                    //break;
                }
            }
            if(presuff == n && j != k-1)
            {
                //cout << "error 2 " << endl;
                continue;
            }

            clean = 1;
            for (int i = start-1; i > pre; -- i)
            {
                if(s[i] == 'X')clean = 0;
            }
            for (int i = fi + 1; i < presuff; ++ i)
            {
                if(s[i] == 'X')clean = 0;
            }
            if(!clean)continue;
       // cout << si << " is ok " << fi << "in " << j <<  endl;
       // cout << pre << " " << presuff << endl;
            for (int i = si; i <= fi; ++ i)
                be1[i] = 1;
            for (int i = pre+1; i < si; ++ i)
                be0[i] = 1;
            for (int i = fi+1; i < presuff; ++ i)
                be0[i] = 1;

        }
    }
    string ans = "";
    for (int i = 0; i < n; ++ i)
    {
        if(be0[i] && be1[i])ans += "?";
        else if(be0[i])ans += "_";
        else if(be1[i])ans += "X";
        else ans += "?";
    }
    return ans;

}

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: 0 / 10