Submission #394083

#TimeUsernameProblemLanguageResultExecution timeMemory
394083cpp219Paint By Numbers (IOI16_paint)C++14
90 / 100
2118 ms338236 KiB
#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 = 2e5 + 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]; suf[i] = suf[i - 1]; if (s[i] == '_') pre[i]++; else if (s[i] == 'X') suf[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"
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...