Submission #1265262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265262		silentloop	Paint By Numbers (IOI16_paint)	C++20	0 / 100	0 ms	320 KiB

paint

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define pb push_back
#define se second
#define fr first
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;

string S;
vector<int> C;
vector<pair<ll, ll>> rangs;

string cons(ll a, ll b, ll po)
{
    ll i, tot = -1, dif, act, j, tam = rangs[po].se - rangs[po].fr + 1;
    for (i = a; i <= b; i++)
    {
        tot++;
        tot = tot + C[i];
    }
    dif = abs(tot - tam);
    if (dif == 0)
    {
        string ans = "";
        for (i = a; i <= b; i++)
        {
            if (i > a)
                ans += "_";
            string ag = "";
            ag.resize(C[i], 'X');
            ans += ag;
        }
        return ans;
    }
    string ret;
    ret.resize(tam, 'X');
    act = -1;
    for (i = 0; i < min(dif, 1ll * tam - 1); i++)
        ret[i] = '?';
    for (i = a; i <= b; i++)
    {
        act++;
        act = act + C[i];
        if (act >= sz(ret))
            break;
        for (j = act; j <= min(act + dif, 1ll * tam - 1); j++)
            ret[j] = '?';
    }
    return ret;
}

string un(string s, string x)
{
    if (s[0] == '.')
        return x;
    for (ll i = 0; i < sz(s); i++)
        if (s[i] != x[i])
            s[i] = '?';
    return s;
}

bool can(ll a, ll b, ll po)
{
    ll i, tam = rangs[po].se - rangs[po].fr + 1, tot = 0, j = 0, act = 0;
    if (a != -1)
    {
        for (i = a; i <= b; i++)
            tot = tot + C[i];
        tot = tot + (b - a);
        if (tot > tam)
            return 0;
    }
    for (i = 0; i < sz(S); i++)
    {
        if (j == a)
            j = b + 1;
        if(i==rangs[po].fr)
        {
            i=rangs[po].se;
            continue;
        }
        if (j >= sz(C))
            return 1;
        if (S[i] == '.')
            act++;
        else
            act = 0;
        if (act == C[j])
        {
            act = 0;
            j++;
            i++;
        }
    }
    if (j >= sz(C))
            return 1;
    return 0;
}

string calc(ll pos)
{
    ll i, j, k;
    string s=".";
    if (can(-1, -1, pos))
    {
        string x;
        x.resize(rangs[pos].se - rangs[pos].fr + 1, '_');
        s = un(s, x);
    }
    for (i = 0; i < sz(C); i++)
    {
        for (j = i; j < sz(C); j++)
        {
            if (can(i, j, pos))
            {
                string x = cons(i, j, pos);
                s = un(s, x);
            }
        }
    }
    return s;
}

std::string solve_puzzle(std::string s, std::vector<int> c)
{
    S = s;
    C = c;
    ll i, in = 0, fin = 0, sig;

    for (i = 0; i < sz(s); i++)
    {
        if (s[i] == '_')
        {
            if (in != i)
                rangs.pb({in, fin - 1});
            in = i + 1;
            fin = in;
            continue;
        }
        fin++;
    }
    if (in < sz(s))
        rangs.pb({in, fin});
    string ans = "";
    sig=0;
    for (i = 0; i < sz(rangs); i++)
    {
        while (sig < sz(s) && s[sig] == '_')
        {
            ans += "_";
            sig++;
        }
        ans += calc(i);
        sig = rangs[i].se + 1;
    }
    while (sig < sz(s) && s[sig] == '_')
    {
        ans += "_";
        sig++;
    }
    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: 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