Submission #592074

#TimeUsernameProblemLanguageResultExecution timeMemory
592074yutabiPaint By Numbers (IOI16_paint)C++14
0 / 100
54 ms21316 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define pb push_back std::string solve_puzzle(std::string s, std::vector<int> c) { s='_'+s+'_'; vector <vector <bool> > DP_l(100007,vector <bool> (107,0)); vector <vector <bool> > DP_r(100007,vector <bool> (107,0)); vector <vector <bool> > DP3(100007,vector <bool> (107,0)); vector <int> next_l; vector <int> next_r; int curr; for(int i=s.size()-1;i>=0;i--) { if(s[i]=='_') { curr=i; } next_l.pb(curr); } reverse(next_l.begin(),next_l.end()); for(int i=0;i<s.size();i++) { if(s[i]=='_') { curr=i; } next_r.pb(curr); } DP_l[0][0]=1; for(int i=0;i<s.size();i++) { for(int j=0;j<=c.size();j++) { if(j!=c.size()) { if(DP_l[i][j] && i+c[j]<=next_l[i] && s[i+c[j]]!='X') { DP_l[i+c[j]+1][j+1]=1; DP3[i][j]=1; } } if(DP_l[i][j] && s[i]!='X') { DP_l[i+1][j]=1; } printf("%d ",(int)DP_l[i][j]); } printf("\n"); } printf("\n"); DP_r[s.size()][c.size()]=1; for(int i=s.size();i>0;i--) { for(int j=c.size();j>=0;j--) { if(j!=0) { if(DP_r[i][j] && next_r[i-1]<=i-1-c[j-1] && s[i-1-c[j-1]]!='X') { DP_r[i-c[j-1]-1][j-1]=1; } } if(DP_r[i][j] && s[i-1]!='X') { DP_r[i-1][j]=1; } printf("%d ",(int)DP_r[i][j]); } printf("\n"); } printf("\n"); curr=10000000; for(int i=s.size()-1;i>=0;i--) { for(int j=0;j<=c.size();j++) { if(j!=c.size()) { if(DP3[i][j] && DP_r[i-1][j]) { for(int k=i;k<min(i+c[j],curr);k++) { if(s[k]=='_' || s[k]=='?') { s[k]='?'; } else { s[k]='X'; } } curr=i; if(s[i-1]=='X' || s[i-1]=='?') { s[i-1]='?'; } else { s[i-1]='_'; } if(s[i+c[j]]=='X' || s[i+c[j]]=='?') { s[i+c[j]]='?'; } else { s[i+c[j]]='_'; } } } if(DP_l[i][j] && DP_l[i+1][j] && DP_r[i+1][j] && DP_r[i][j]) { if(s[i]=='X' || s[i]=='?') { s[i]='?'; } else { s[i]='_'; } } } } string nw=""; for(int i=1;i<s.size()-1;i++) { nw+=s[i]; } return nw; }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
paint.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<s.size();i++)
      |                 ~^~~~~~~~~
paint.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<=c.size();j++)
      |                     ~^~~~~~~~~~
paint.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(j!=c.size())
      |                ~^~~~~~~~~~
paint.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j=0;j<=c.size();j++)
      |                     ~^~~~~~~~~~
paint.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             if(j!=c.size())
      |                ~^~~~~~~~~~
paint.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i=1;i<s.size()-1;i++)
      |                 ~^~~~~~~~~~~
#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...