Submission #587726

#	Time	Username	Problem	Language	Result	Execution time	Memory
587726		tranxuanbach	Paint By Numbers (IOI16_paint)	C++17	100 / 100	424 ms	56484 KiB

paint

#ifndef FEXT

#include "paint.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 2e5 + 5, M = 1e2 + 5;

int n, m;
string s;
int a[M];

int can0[N], can1[N];

bool canrange0(int l, int r){
    l = max(l, 1); r = min(r, n);
    if (l > r){
        return 1;
    }
    if (can0[r] - can0[l - 1] == r - l + 1){
        return 1;
    }
    return 0;
}

bool canrange1(int l, int r){
    l = max(l, 1); r = min(r, n);
    if (l > r){
        return 1;
    }
    if (can1[r] - can1[l - 1] == r - l + 1){
        return 1;
    }
    return 0;
}

bool dp[M][N], vis[M][N];

int set0[N], set1[N];

void dfs_state(int i, int j){
    vis[i][j] = 1;
    if (canrange0(j, j)){
        if (dp[i][j - 1]){
            set0[j]++; set0[j + 1]--;
            if (!vis[i][j - 1]){
                dfs_state(i, j - 1);
            }
        }
    }
    bool ck = canrange1(j - a[i] + 1, j) & canrange0(j - a[i], j - a[i]);
    if (i == 1){
        ck &= canrange0(1, j - a[i]);
    }
    if (i == m){
        ck &= canrange0(j + 1, n);
    }
    if (ck){
        if (i == 1 or dp[i - 1][j - a[i] - 1]){
            set1[j - a[i] + 1]++; set1[j + 1]--;
            if (j - a[i] > 0){
                set0[j - a[i]]++; set0[j - a[i] + 1]--;
            }
            if (i == 1 and j - a[i] > 0){
                set0[1]++; set0[j - a[i] + 1]--;
            }
            if (i == m and j + 1 <= n){
                set0[j + 1]++; set0[n + 1]--;
            }
            if (i - 1 > 0 and j - a[i] - 1 > 0 and !vis[i - 1][j - a[i] - 1]){
                dfs_state(i - 1, j - a[i] - 1);
            }
        }
    }
}

string ans;

string solve_puzzle(string _s, vi _c){
    n = isz(_s); m = isz(_c);
    s = ' ' + _s;
    ForE(i, 1, m){
        a[i] = _c[i - 1];
    }

    ForE(i, 1, n){
        can0[i] = can0[i - 1] + (s[i] != 'X');
    }
    ForE(i, 1, n){
        can1[i] = can1[i - 1] + (s[i] != '_');
    }

    ans = ' ' + string(n, '?');

    ForE(i, 1, m){
        ForE(j, (i == 1 ? a[i] : a[i] + 1), n){
            if (canrange0(j, j)){
                dp[i][j] |= dp[i][j - 1];
            }
            bool ck = canrange1(j - a[i] + 1, j) & canrange0(j - a[i], j - a[i]);
            if (i == 1){
                ck &= canrange0(1, j - a[i]);
            }
            if (i == m){
                ck &= canrange0(j + 1, n);
            }
            if (ck){
                if (i == 1){
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] |= dp[i - 1][j - a[i] - 1];
                }
            }
            // cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        }
    }
    assert(dp[m][n]);
    /*{
        int i = m, j = n;
        while (i){
            bool ck = canrange1(j - a[i] + 1, j) & canrange0(j - a[i], j - a[i]);
            if (i == 1){
                ck &= canrange0(1, j - a[i]);
            }
            if (i == m){
                ck &= canrange0(j + 1, n);
            }
            if (ck){
                if (i == 1 or dp[i - 1][j - a[i] - 1]){
                    ForE(tj, j - a[i] + 1, j){
                        sright[tj] = 'X';
                    }
                    posright[i] = j - a[i] + 1;
                    j -= a[i] + 1; i--;
                    continue;
                }
            }
            j--;
        }
    }*/

    /*memset(dp, 0, sizeof(dp));
    FordE(i, m, 1){
        FordE(j, n - (i == m ? a[i] : a[i] + 1) + 1, 1){
            if (canrange0(j, j)){
                dp[i][j] |= dp[i][j + 1];
            }
            bool ck = canrange1(j, j + a[i] - 1) & canrange0(j + a[i], j + a[i]);
            if (i == m){
                ck &= canrange0(j + a[i], n);
            }
            if (i == 1){
                ck &= canrange0(1, j - 1);
            }
            if (ck){
                if (i == m){
                    dp[i][j] = 1;
                }
                else{
                    dp[i][j] |= dp[i + 1][j + a[i] + 1];
                }
            }
        }
    }
    assert(dp[1][1]);
    {
        int i = 1, j = 1;
        while (i <= m){
            bool ck = canrange1(j, j + a[i] - 1) & canrange0(j + a[i], j + a[i]);
            if (i == m){
                ck &= canrange0(j + a[i], n);
            }
            if (i == 1){
                ck &= canrange0(1, j - 1);
            }
            if (ck){
                if (i == m or dp[i + 1][j + a[i] + 1]){
                    ForE(tj, j, j + a[i] - 1){
                        sleft[tj] = 'X';
                    }
                    posleft[i] = j;
                    j += a[i] + 1; i++;
                    continue;
                }
            }
            j++;
        }
    }*/

    dfs_state(m, n);

    ForE(i, 1, n){
        set0[i] += set0[i - 1];
        set1[i] += set1[i - 1];
    }
    ForE(i, 1, n){
        if (set0[i] == 0){
            ans[i] = 'X';
        }
        if (set1[i] == 0){
            ans[i] = '_';
        }
    }

    ans.erase(0, 1);
    return ans;
}

#ifdef FEXT

const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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