Submission #1210503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210503		Zbyszek99	Paint By Numbers (IOI16_paint)	C++20	7 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int n,k;
int segs[102];
bool dp_pref[200001][102];
bool dp_suf[200002][102];
int pref1[200001];
int pref0[200001];
int can1[200001];
string ans;

string solve_puzzle(string s, vi c) 
{
    rep(i,siz(c))
    {
        segs[i+1] = c[i];
    }
    n = siz(s);
    k = siz(c);
    ans = s;
    rep2(i,1,n)
    {
        pref1[i] = pref1[i-1];
        pref0[i] = pref0[i-1];
        if(s[i-1] == 'X') pref1[i]++;
        else if(s[i-1] == '_') pref0[i]++;
    }
    dp_pref[0][0] = 1;
    rep2(i,1,n)
    {
        if(pref1[i] == 0) dp_pref[i][0] = 1;
        rep2(kk,1,k)
        {
            if(i - segs[kk] >= 0 && (kk != 1 ? i-segs[kk]-1 >= 0 && dp_pref[i-segs[kk]-1][kk-1] : pref1[i-segs[kk]] == 0) && pref0[i] - pref0[i-segs[kk]] == 0)
            {
                dp_pref[i][kk] = 1;
            }
            if(s[i-1] != 'X' && dp_pref[i-1][kk])
            {
                dp_pref[i][kk] = 1;
            }
        }
    }
    dp_suf[n+1][k+1] = 1;
    for(int i = n; i >= 1; i--)
    {
        if(pref1[i-1] == pref1[n]) dp_suf[i][k+1] = 1;
        rep2(kk,1,k)
        {
            if(i + segs[kk] <= n+1 && (kk != k ? i+segs[kk]+1 <= n+1 && dp_suf[i+segs[kk]+1][kk+1] : pref1[n] == pref1[i+segs[kk]-1]) && pref0[i+segs[kk]-1] - pref0[i-1] == 0)
            {
                dp_suf[i][kk] = 1;
            }
            if(s[i-1] != 'X' && dp_suf[i+1][kk])
            {
                dp_suf[i][kk] = 1;
            }
        }
    }
    rep2(kk,1,k)
    {
        rep2(i,1,n-segs[kk]+1)
        {
            if(pref0[i+segs[kk]-1] - pref0[i-1] == 0 && (i != 1 || kk != 1 ? (i != 1 && dp_pref[i-2][kk-1] && s[i-2] != 'X') : pref1[i-1] == 0) && (i != n-segs[kk]+1 && kk != k ? (i != n-segs[kk]+1 && dp_suf[i+segs[kk]+1][kk+1] && s[i+segs[kk]-2] != 'X') : pref1[n] == pref1[i+segs[kk]-1]))
            {
                can1[i]++;
                can1[i+segs[kk]]--;
            }
        }
    }
    int cur = 0;
    rep2(i,1,n)
    {
        cur += can1[i];
        can1[i] = cur;
    }
    rep2(i,1,n)
    {
        if(s[i-1] != '.') continue;
        bool c0 = 0;
        bool c1 = (can1[i] > 0);
        rep(kk,k+1)
        {
            if(dp_pref[i-1][kk] && dp_suf[i+1][kk+1])
            {
                c0 = 1;
            }
        }
        if(c0 && c1) ans[i-1] = '?';
        else if(c0) ans[i-1] = '_';
        else ans[i-1] = 'X';
    }
    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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10