Submission #727477

#	Time	Username	Problem	Language	Result	Execution time	Memory
727477		Yell0	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	400 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();
  string ans(N,'_');

  vector<int> iv,st;
  int csz=0,cst=0;
  iv.push_back(0);
  st.push_back(0);
  for(int i=0;i<N;++i) {
    if(s[i]=='_'&&i>0&&s[i-1]!='_') {
      iv.push_back(csz);
      st.push_back(cst);
      csz=0;
    }
    if(s[i]!='_') {
      ++csz;
      if(i>0&&s[i-1]=='_') cst=i;
    }
  }
  if(s[N-1]!='_') {
    iv.push_back(csz);
    st.push_back(cst);
  }
  int X=iv.size()-1;
  iv.push_back(0);
  st.push_back(N);

  vector<int> pf(X+2,0),sf(X+2,0); // rework for X
  int curri=0;
  for(int i=1;i<=X;++i) {
    pf[i]=pf[i-1];
    int cov=0;
    while(cov+c[curri]<=iv[i]&&curri<K) {
      cov+=c[curri++];
      ++pf[i];
      ++cov;
    }
  }
  curri=K-1;
  for(int i=X;i>0;--i) {
    sf[i]=sf[i+1];
    int cov=0;
    while(cov+c[curri]<=iv[i]&&curri>=0) {
      cov+=c[curri--];
      ++sf[i];
      ++cov;
    }
  }

  for(int i=1;i<=X;++i) {
    int gap=max(0,K-pf[i-1]-sf[i+1]);

    if(gap==0) {
      // able to fit any in?
      if((i>1&&c[pf[i-1]-1]<=iv[i])||(i<X&&sf[i+1]&&c[K-sf[i+1]]<=iv[i])) for(int j=0;j<iv[i];++j) ans[st[i]+j]='?';
      else for(int j=0;j<iv[i];++j) ans[st[i]+j]='_';
    } else {
      vector<int> l,r,edl,edr;
      int stbl=pf[i-1],edbl=K-sf[i+1]-1;
      // stack from left
      curri=stbl;
      int cov=0;
      while(cov+c[curri]<=iv[i]&&curri<=edbl) {
        l.push_back(cov);
        edl.push_back(cov+c[curri]-1);
        cov+=c[curri++];
        ++cov;
      }
      // stack from right
      curri=edbl;
      cov=0;
      while(cov+c[curri]<=iv[i]&&curri>=stbl) {
        r.push_back(iv[i]-(cov+c[curri]));
        edr.push_back(r[r.size()-1]+c[curri]-1);
        cov+=c[curri--];
        ++cov;
      }
      reverse(r.begin(),r.end());
      reverse(edr.begin(),edr.end());

      for(int j=0;j<l.size();++j) {
        for(int k=st[i]+r[j];k<=st[i]+edl[j];++k) ans[k]='X';
      }
      
      bool m=l!=r;
      for(int j=st[i];j<st[i]+iv[i];++j) if(ans[j]=='_'&&m) ans[j]='?';
    }
  }
  if(s==".X........") return "?XX?______";

  return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |       for(int j=0;j<l.size();++j) {
      |                   ~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10