Submission #727625

#	Time	Username	Problem	Language	Result	Execution time	Memory
727625		Yell0	Paint By Numbers (IOI16_paint)	C++17	100 / 100	690 ms	182348 KiB

paint

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

string solve_puzzle(string s,vector<int> c) {
  int N=s.size(),K=c.size();
  s.insert(s.begin(),'.');
  c.insert(c.begin(),0);

  // pf/sf
  vector<int> pfb(N+2,0),pfw(N+2,0);
  for(int i=1;i<=N;++i) {
    pfb[i]=pfb[i-1]+(s[i]=='X');
    pfw[i]=pfw[i-1]+(s[i]=='_');
  }

  // dp
  vector<vector<int>> pfdp(N+3,vector<int>(K+3,0)),sfdp(N+3,vector<int>(K+3,0));
  for(int i=0;i<=N;++i) {
    for(int j=0;j<=K;++j) {
      if(!j) {
        pfdp[i][j]=!pfb[i];
        continue;
      }
      if(c[j]>i) {
        pfdp[i][j]=0;
        continue;
      }
      bool fb,fw;
      if(s[i-c[j]]=='X'||(pfw[i]-pfw[i-c[j]])) fb=0;
      else fb=pfdp[max(0,i-c[j]-(j>1))][j-1];
      fw=pfdp[i-1][j];

      if(s[i]=='X') pfdp[i][j]=fb;
      else if(s[i]=='_') pfdp[i][j]=fw;
      else pfdp[i][j]=fb||fw;
    }
  }
  for(int i=N+1;i>0;--i) {
    for(int j=K+1;j>0;--j) {
      if(j==K+1) {
        sfdp[i][j]=!(pfb[N]-pfb[i-1]);
        continue;
      }
      if(c[j]>N-i+1) {
        sfdp[i][j]=0;
        continue;
      }
      bool fb,fw;
      if(s[i+c[j]]=='X'||(pfw[i+c[j]-1]-pfw[i-1])) fb=0;
      else fb=sfdp[min(N+1,i+c[j]+(j<K))][j+1];
      fw=sfdp[i+1][j];

      if(s[i]=='X') sfdp[i][j]=fb;
      else if(s[i]=='_') sfdp[i][j]=fw;
      else sfdp[i][j]=fb||fw;
    }
  }

  vector<bool> b(N+2),w(N+2);
  // can be white?
  for(int i=1;i<=N;++i) {
    if(s[i]=='_') w[i]=1;
    else if(s[i]=='X') w[i]=0;
    else for(int j=0;j<=K;++j) if(pfdp[i-1][j]&&sfdp[i+1][j+1]) w[i]=1;
  }
  // can be black
  vector<int> diff(N+2);
  for(int i=1;i<=K;++i) {
    for(int j=1;j+c[i]-1<=N;++j) {
      bool v=1;
      if(s[j-1]=='X'||s[j+c[i]]=='X') v=0;
      if(pfw[j+c[i]-1]-pfw[j-1]) v=0;
      if(!pfdp[max(0,j-2)][i-1]||!sfdp[min(N+1,j+c[i]+1)][i+1]) v=0;
      if(v) {
        ++diff[j];
        --diff[j+c[i]];
      }
    }
  }
  int sum=0;
  for(int i=1;i<=N;++i) {
    sum+=diff[i];
    b[i]=sum>0;
  }
  
  string ans="";
  for(int i=1;i<=N;++i) {
    if(w[i]&&b[i]) ans.push_back('?');
    else if(w[i]) ans.push_back('_');
    else if(b[i]) ans.push_back('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