Submission #394116

#	Time	Username	Problem	Language	Result	Execution time	Memory
394116		arwaeystoamneg	Paint By Numbers (IOI16_paint)	C++17	100 / 100	566 ms	10060 KiB

paint

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
#ifndef arwaeystoamneg
#include "paint.h"
#endif

const int MAX = 200005;
int n, k, prefix[MAX], b[101], upd[MAX], su[MAX];
bitset<101>dp[MAX], dp1[MAX];
bitset<MAX>u;
string a;
std::string solve_puzzle(std::string s, std::vector<int> c) 
{
    a = s;
    n = sz(s);
    k = sz(c);
    F0R(i, k)b[i] = c[i];

    F0R(i, n)
    {
        prefix[i + 1] = prefix[i] + (a[i] == '_');
    }
    F0R(i, n + 1)F0R(j, k + 1)dp[i][j] = 0, dp1[i][j] = 0;
    dp[0][0] = 1;
    F0R(i, n)
    {
        F0R(j, k + 1)
        {
            if (!dp[i][j])continue;
            if (j != k)
            {
                if (i + b[j] > n)continue;
                // if all X
                if (prefix[i + b[j]] - prefix[i] == 0)
                {
                    if (j == k - 1)
                        dp[i + b[j]][j + 1] = 1;
                    else if (a[i + b[j]] != 'X')
                        dp[i + b[j] + 1][j + 1] = 1;
                }
            }
            // if _
            if (a[i] != 'X')
                dp[i + 1][j] = 1;
        }
    }

    dp1[n][k] = 1;
    R0F(i, n)
    {
        F0R(j, k + 1)
        {
            if (j != k)
            {
                if (i + b[j] > n)continue;
                // if all X
                if (prefix[i + b[j]] - prefix[i] == 0)
                {
                    if (j == k - 1 && dp1[i + b[j]][j + 1])
                        dp1[i][j] = 1;
                    else if (a[i + b[j]] != 'X' && dp1[i + b[j] + 1][j + 1])
                        dp1[i][j] = 1;
                }
            }
            // if _
            if (a[i] != 'X' && dp1[i + 1][j])
                dp1[i][j] = 1;
        }
    }
    F0R(i, n)
    {
        F0R(j, k + 1)
        {
            if (dp[i][j] && dp1[i][j])
            {
                if (j != k)
                {
                    assert(i + b[j] <= n);
                    if (prefix[i + b[j]] - prefix[i] == 0)
                    {
                        if (j == k - 1)
                        {
                            if (dp1[i + b[j]][j + 1])
                            {
                                upd[i + b[j]]--;
                                upd[i]++;
                            }
                        }
                        else if (a[i + b[j]] != 'X')
                        {
                            if (dp1[i + b[j] + 1][j + 1])
                            {
                                upd[i + b[j]]--;
                                upd[i]++;
                                u[i + b[j]] = 1;
                            }
                        }
                    }
                }
                if (a[i] != 'X')
                {
                    if (dp1[i + 1][j])
                    {
                        u[i] = 1;
                    }
                }
            }
        }
    }

    F0R(i, n)su[i + 1] = su[i] + upd[i];
    string res;
    F0R(i, n)
    {
        int ans = 0;
        if (su[i + 1])
        {
            ans++;
        }
        if (u[i])
        {
            ans += 2;
        }
        if (ans == 0)assert(0);
        if (ans == 1)res.pb('X');
        if (ans == 2)res.pb('_');
        if (ans == 3)res.pb('?');
    }
    return res;
}


#ifdef arwaeystoamneg

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

int main() 
{
    setIO("");
    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

• 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