Submission #1276610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276610		k12_khoi	Paint By Numbers (IOI16_paint)	C++17	32 / 100	67 ms	444 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,k,x;
int sz[N],pre[N],suf[N];
bool f[N],g[N];
string s;
vector <int> c;

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

    int n=s.size();

    string t=s;

    function <void(int)> ql = [&] (int i) -> void
    {
        if (i==n)
        {
            int cur=0;

            for (int i=0;i<n;i++)
            sz[i]=0;

            for (int i=0;i<n;i++)
            {
                if (t[i]=='_')
                {
                    if (sz[cur]) cur++;
                }
                else sz[cur]++;
            }

            if (sz[cur]) cur++;


            if (cur==k)
            {
                for (int i=0;i<k;i++)
                if (c[i]!=sz[i]) return;

                for (int i=0;i<n;i++)
                if (t[i]=='X') f[i]=true;
                else g[i]=true;
            }

            return;
        }


        if (s[i]=='.')
        {
            t[i]='X';
            ql(i+1);
            t[i]='_';
            ql(i+1);
        }
        else ql(i+1);
    };

    auto sub3 = [&] ()
    {
        int sum=k-1;

        for (int i=0;i<k;i++)
        sum+=c[i];

        if (sum==n)
        {
            int cur=0;

            for (int i=0;i<k;i++)
            {
                for (int j=cur;j<cur+c[i];j++)
                ans[j]='X';

                if (i!=k-1)
                {
                    ans[cur+c[i]]='_';
                    cur+=c[i]+1;
                }
            }
        }
        else
        {
            int cur=0;

            for (int i=0;i<k;i++)
            {
                pre[cur+c[i]]++;
                cur+=c[i]+1;
            }

            cur=n-1;
            for (int i=k-1;i>=0;i--)
            {
                suf[cur-c[i]]++;
                cur-=c[i]+1;
            }

            pre[0]=0;
            for (int i=1;i<n;i++)
            pre[i]+=pre[i-1];

            suf[n-1]=0;
            for (int i=n-2;i>=0;i--)
            suf[i]+=suf[i+1];

            for (int i=0;i<n;i++)
            if (pre[i]+suf[i]>=k) ans[i]='?';
            else ans[i]='X';
        }
        return ans;
    };

    if (n>20) return sub3();


    ql(0);


    for (int i=0;i<n;i++)
    if (ans[i]=='.')
    {
        if (f[i] and g[i]) ans[i]='?';
        else if (f[i]) ans[i]='X';
        else ans[i]='_';
    }

    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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10