제출 #727516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727516		Yell0	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	212 KiB

paint

#include <bits/stdc++.h>

using namespace std;

string solve_puzzle(string s,vector<int> c) {
  int N=s.size(),K=c.size();
  string ans(N,'_');

  vector<int> iv,st,xiv,xst;
  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;

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

  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?
      bool fits=0;
      if(i==1) fits=c[0]<=iv[i];
      else if(i==X) fits=c[K-1]<=iv[i];
      else for(int j=max(0,K-sf[i+1]-1);j<=min(K-1,pf[i-1]);++j) if(c[j]<=iv[i]) fits=1;
      if(fits) 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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