Submission #1204404

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

paint

#include <bits/stdc++.h>
#include "paint.h"
#define pb push_back
using namespace std;
const int maxn = 200005, maxk = 205;
int n, k;
int dp[maxn][maxk], suff[maxn][maxk];
int be1[maxn], be0[maxn];

int pref0[maxn], pref1[maxn];
int get0(int l, int r)
{
    if(r < l)return 0;
    int rem = 0;
    if(l > 0)rem = pref0[l-1];
    return pref0[r] - rem;
}
int get1(int l, int r)
{
    if(r < l)return 0;
    int rem = 0;
    if(l > 0)rem = pref1[l-1];
    return pref1[r] - rem;
}
int last[maxn], nxt[maxn];
vector < int > p[maxk], g[maxk];
std::string solve_puzzle(std::string s, std::vector<int> c)
{
    n = s.size();
    //cout << n << endl;
    k = c.size();
    /// pref
    if(s[0] == '_')pref0[0] = 1;
    else pref0[0] = 0;
    for (int i = 1; i < n; ++ i)
    {
        pref0[i] = pref0[i-1];
        if(s[i] == '_')pref0[i] ++;
    }
    if(s[0] == 'X')pref1[0] = 1;
    else pref1[0] = 0;
    for (int i = 1; i < n; ++ i)
    {
        pref1[i] = pref1[i-1];
        if(s[i] == 'X')pref1[i] ++;
    }

    int currlast = -1;
    for (int i = 0; i < n; ++ i)
    {
        if(s[i] == 'X')currlast = i;
        last[i] = currlast;
    }
    int currnxt = n;
    for (int i = n-1; i >= 0; -- i)
    {
        if(s[i] == 'X')currnxt = i;
        nxt[i] = currnxt;
    }
    for (int j = 0; j < k; ++ j)
    {

        for (int i = 0; i < n; ++ i)
        {
            if(i < n-1 && s[i+1] == 'X')continue;
            int len = c[j];
            int endpoint = i - len + 1;
            if(endpoint < 0)continue;

            int cnt0 = get0(endpoint, i);
            if(cnt0)continue;

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

            if(j == 0)
            {
                int cnt1 = get1(0, endpoint-1);
                if(!cnt1)dp[i][j] = 1;
                continue;
            }


            if(s[endpoint-1] == 'X')continue;
            assert(endpoint > 0);
            int checkfree = 1;

            int arefree = last[endpoint-1];

            int lt = 0, rt = p[j-1].size()-1, mid, ans = endpoint;
            while(lt <= rt)
            {
                mid = (lt + rt)/2;
                if(p[j-1][mid] >= arefree)
                {
                    ans = p[j-1][mid];
                    rt = mid - 1;
                }
                else lt = mid + 1;
            }

            if(ans <= endpoint - 2)
            {
                dp[i][j] = 1;

            }
        }
        for (int i = 0; i < n; ++ i)
            if(dp[i][j])p[j].push_back(i);
        sort(p[j].begin(), p[j].end());

    }
    for (int j = k-1; j >= 0; -- j)
    {
        for (int i = n-1; i >= 0; -- i)
        {
            if(i > 0 && s[i-1] == 'X')
                continue;

            int len = c[j];
            int endpoint = i + len - 1;
            if(endpoint > n - 1)continue;

            int cnt0 = get0(i, endpoint);
            if(cnt0)continue;

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

            if(j == k-1)
            {
                int cnt1 = get1(endpoint+1, n-1);
                if(!cnt1)suff[i][j] = 1;
                continue;
            }
            int checkfree = 1;
            if(s[endpoint+1] == 'X')continue;
            int arefree = nxt[endpoint+1];
            int found = 0;
            /*int found = 0;
            ///endpoint+2, arefree
            for (auto x: g[j-1])
            {
                if(x >= endpoint+2 && x <= arefree)found = 1;
            }*/
             int lt = 0, rt = g[j+1].size()-1, mid, ans = arefree+1;
            while(lt <= rt)
            {
                mid = (lt + rt)/2;
                if(g[j+1][mid] >= endpoint+2)
                {
                    ans = g[j+1][mid];
                    rt = mid - 1;
                }
                else lt = mid + 1;
            }

            if(ans <= arefree)
            {
                suff[i][j] = 1;

            }
            /*for (int index = endpoint + 2; index <= min(arefree, n-1); ++ 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;

            }*/
        }
        for (int i = 0; i < n; ++ i)
            if(suff[i][j])g[j].push_back(i);
        sort(g[j].begin(), g[j].end());

    }
    for (int j = 0; j < k; ++ j)
    {
        int len = c[j];
        for (int start = 0; start < n; ++ start)
        {

            int si = start;
            int fi = start + len - 1;
            if(fi >= n)
            {

                continue;
            }
            int cnt0 = get0(si, fi);
            if(cnt0)
                continue;

            int cleanbef = si;
            if(si > 0)cleanbef = last[si-1]+1;

            int cleanaft = fi;
            if(fi < n-1)cleanaft = nxt[fi+1] - 1;

            int pre = -1;
            for (int i = start - 2; i >= 0; -- i)
            {
                if(j - 1 >= 0 && dp[i][j-1])pre = i;
                if(i < cleanbef)break;
            }
            if(pre == -1 && j != 0)continue;
            if(pre == -1 && j == 0)
            {
                if(cleanbef == 0)pre = -1;
                else continue;
            }
            int presuff = n;

            for (int i = fi + 2; i < n; ++ i)
            {

                if(j + 1 < n && suff[i][j+1])
                    presuff = i;
                if(i > cleanaft)break;
            }
            if(presuff == n && j != k-1)
            {

                continue;
            }
            if(presuff == n && j == k-1)
            {
                if(cleanaft == n-1)presuff = n;
                else continue;

            }

            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