Submission #1020451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020451		huutuan	Paint By Numbers (IOI16_paint)	C++14	100 / 100	339 ms	333312 KiB

paint

#include "paint.h"

#include <cstdlib>

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+10, K=210;
int f1[N][K], f2[N][K], n, k, nxt[N];

string solve_puzzle(string s, vector<int> c) {
   n=s.size(), k=c.size();
   s=" "+s; c.insert(c.begin(), 0);
   nxt[n+1]=n+1;
   for (int i=n; i>=1; --i){
      if (s[i]=='_') nxt[i]=i;
      else nxt[i]=nxt[i+1];
   }
   f1[0][0]=f1[0][1]=1;
   for (int i=1; i<=n; ++i){
      for (int j=1; j<=k*2+1; ++j){
         if (j&1){
            if (s[i]!='X'){
               f1[i][j]|=f1[i-1][j];
               f1[i][j]|=f1[i-1][j-1];
            }
         }else{
            int len=c[j>>1];
            if (i>=len && nxt[i-len+1]>i){
               f1[i][j]|=f1[i-len][j-1];
            }
         }
      }
   }
   f2[n+1][k*2+1]=1; f2[n+1][k*2+2]=1;
   for (int i=n; i>=1; --i){
      for (int j=1; j<=k*2+1; ++j){
         if (j&1){
            if (s[i]!='X'){
               f2[i][j]|=f2[i+1][j];
               f2[i][j]|=f2[i+1][j+1];
            }
         }else{
            int len=c[j>>1];
            if (i+len-1<=n && nxt[i]>i+len-1){
               f2[i][j]|=f2[i+len][j+1];
            }
         }
      }
   }
   string ans(n, '?');
   vector<int> d(n+1), check0(n+1), check1(n+1);
   for (int i=1; i<=n; ++i){
      for (int j=1; j<=k*2+1; ++j){
         if (j&1){
            if (f1[i][j] && (f2[i+1][j] || f2[i+1][j+1])){
               check0[i]=1;
            }
         }else{
            int len=c[j>>1];
            if (f1[i][j] && f2[i+1][j+1]){
               int l=i-len+1, r=i;
               ++d[l];
               if (r<n) --d[r+1];
            }
         }
      }
   }
   partial_sum(d.begin(), d.end(), check1.begin());
   for (int i=1; i<=n; ++i){
      if (check0[i] && !check1[i]) ans[i-1]='_';
      if (check1[i] && !check0[i]) ans[i-1]='X';
   }
   return ans;
}

• 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