Submission #1107011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107011		SonicML	Paint By Numbers (IOI16_paint)	C++14	0 / 100	1 ms	4432 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

string cc;

int const NMAX = 5000;
int dp[2][1 + NMAX][1 + NMAX + 1][2];

void computeDp(string s, string cc, int id) {
  
  dp[id][0][0][0] = 1;
  for(int i = 1;i <= s.size();i++) {
    if(s[i-1] != 'X') {
      dp[id][i][0][0] = dp[id][i-1][0][0];
      int tempK = cc.size()+1;
      dp[id][i][tempK][0] = (dp[id][i-1][tempK][0] | dp[id][i-1][tempK-1][1]);
    }
    for(int k = 1;k <= i && k <= cc.size();k++) {
      // try white
      if(s[i-1] != 'X' && cc[k-1] == '_') {
        dp[id][i][k][0] = (dp[id][i-1][k][0] | dp[id][i-1][k-1][1]);
      }
      // try black
      if(s[i-1] != '_' && cc[k-1] == 'X') {
        dp[id][i][k][1] = (dp[id][i-1][k-1][0] | dp[id][i-1][k-1][1]);
      }
      //cerr << "{" << dp[id][i][k][0] << ", " << dp[id][i][k][1] << "}, ";
    }
    //cerr << '\n';
  }
}	

void buildDp(string s, string cc) {
  computeDp(s, cc, 0);
  reverse(s.begin(), s.end());
  reverse(cc.begin(), cc.end());
  computeDp(s, cc, 1);  
}

string solve_puzzle(string s, vector <int> c) {
  string result;
  for(int j = 0;j < c[0];j++) {
    cc.push_back('X');
  } 
  for(int i = 1;i < c.size();i++) {
    cc.push_back('_');
    for(int j = 0;j < c[i];j++) {
      cc.push_back('X');
    }
  }
  //cerr << cc << '\n';
  buildDp(s, cc);
  result.resize(s.size());
  for(int i = 1;i <= s.size();i++) {
    bool canWhite = false, canBlack = false;
    for(int k = 0;k <= cc.size()+1;k++) {
      if(dp[0][i][k][0] && dp[1][s.size()-i+1][cc.size()-k+1][0]) {
	canWhite = true;
      }
      if(dp[0][i][k][1] && dp[1][s.size()-i+1][cc.size()-k+1][1]) {
        canBlack = true;
      }
    }    
    if(canWhite && canBlack) {
      result.push_back('?');
    } else if(canWhite) {
      result.push_back('_');
    } else if(canBlack) { 
      result.push_back('X');
    } else {
      result.push_back('?');
    }
  }
  //cerr << s << ' ' << result << '\n';
  return result;
}

Compilation message (stderr)

paint.cpp: In function 'void computeDp(std::string, std::string, int)':
paint.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(int i = 1;i <= s.size();i++) {
      |                 ~~^~~~~~~~~~~
paint.cpp:22:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int k = 1;k <= i && k <= cc.size();k++) {
      |                             ~~^~~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 1;i < c.size();i++) {
      |                 ~~^~~~~~~~~~
paint.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i = 1;i <= s.size();i++) {
      |                 ~~^~~~~~~~~~~
paint.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int k = 0;k <= cc.size()+1;k++) {
      |                   ~~^~~~~~~~~~~~~~

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