Submission #394085

#	Time	Username	Problem	Language	Result	Execution time	Memory
394085		cpp219	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2131 ms	496348 KiB

paint

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 3e5 + 9;
const ll mod = 1e9 + 7;
ll a[N],k,n;
ll dp1[N][203],dp2[N][203];
ll CanWhite[N],CanBlack[N],pre[N],suf[N];
string s;

bool Any(ll L,ll R){
    return pre[R] - pre[L - 1];
}

ll f1(ll n,ll k){
    if (k < 0) return 0;
    if (n < 1) return (k == 0);
    if (dp1[n][k] != -1) return dp1[n][k];
    ll ans = 0,nxt = n - a[k] - 1;
    if (s[n] == 'X' && n - a[k] + 1 > 0 && !Any(nxt + 2,n) && s[nxt + 1] != 'X') ans = f1(nxt,k - 1);
    if (s[n] == '_') ans = f1(n - 1,k);
    if (s[n] == '.'){
        ans = f1(n - 1,k);
        if (n - a[k] + 1 > 0 && !Any(nxt + 2,n) && s[nxt + 1] != 'X') ans |= f1(nxt,k - 1);
    }
    return dp1[n][k] = ans;
}

ll f2(ll pos,ll cur){
    if (cur > k + 1) return 0;
    if (pos > n) return (cur == k + 1);
    if (dp2[pos][cur] != -1) return dp2[pos][cur];
    ll ans = 0,nxt = pos + a[cur] + 1; //cout<<nxt; exit(0);
    if (s[pos] == 'X' && pos + a[cur] - 1 <= n && !Any(pos,nxt - 2) && s[nxt - 1] != 'X') ans = f2(nxt,cur + 1);
    if (s[pos] == '_') ans = f2(pos + 1,cur);
    if (s[pos] == '.'){
        ans = f2(pos + 1,cur);
        if (pos + a[cur] - 1 <= n && !Any(pos,nxt - 2) && s[nxt - 1] != 'X') ans |= f2(nxt,cur + 1);
    }
    return dp2[pos][cur] = ans;
}

string solve_puzzle(string p,vector<ll> c){
    n = p.size(); k = c.size(); s = " " + p;
    for (ll i = 1;i <= k;i++) a[i] = c[i - 1];
    for (ll i = 1;i <= n;i++){
        pre[i] = pre[i - 1];
        if (s[i] == '_') pre[i]++;
    }
    //cout<<pre[4]; exit(0);
    memset(dp1,-1,sizeof(dp1)); memset(dp2,-1,sizeof(dp2));
    string ans;
    for (ll i = 1;i <= n;i++){
        for (ll j = 0;j <= k;j++){
            CanWhite[i] |= (f1(i - 1,j) & f2(i + 1,j + 1));
        }
        //cout<<f2(2,1); exit(0);
        for (ll j = 1;j <= k;j++){
            ll start = i - a[j] + 1; if (start < 1) continue;
            if (s[start - 1] != 'X' && !Any(start,i) && s[i + 1] != 'X'){
                //cout<<f(5,1); exit(0);
                //cout<<f1(i,j)<<" "<<f2(i + 2,j + 1)<<"\n";
                if (f1(start - 2,j - 1) & f2(i + 2,j + 1)){
                    CanBlack[start]++,CanBlack[i + 1]--;
                    //cout<<start<<" "<<i<<" "<<j<<"\n";
                }
            }
        }
        //exit(0);
    }
    //exit(0);
    for (ll i = 1;i <= n;i++){
        CanBlack[i] += CanBlack[i - 1]; //cout<<CanBlack[i]<<" ";
        ll p = CanBlack[i],q = CanWhite[i];
        if (s[i] == '_') p = 0,q = 1;
        if (s[i] == 'X') p = 1,q = 0;
        if (p && q) ans += '?';
        else if (!p && q) ans += '_';
        else ans += 'X';
    }
    //exit(0);
    return ans;
}

Compilation message (stderr)

paint.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
paint.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |

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