Submission #1107064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107064		SonicML	Paint By Numbers (IOI16_paint)	C++14	100 / 100	242 ms	161308 KiB

paint

#include "paint.h"
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int const NMAX = 2e5;
int const KMAX = 100;
int dp[2][1 + NMAX][1 + KMAX];
int preWhite[1 + NMAX];
int smenBlack[1 + NMAX];

void buildPreWhite(string s) {
  for(int i = 1;i <= s.size();i++) { 
    preWhite[i] = preWhite[i-1];
    if(s[i-1] == '_') {
      preWhite[i]++;
    }
  }
}
void computeDp(int id, string s, vector <int> c) {
  dp[id][0][0] = 1;
  buildPreWhite(s);
  for(int i = 1;i <= s.size();i++) {
    if(s[i-1] != 'X') {
      dp[id][i][0] = dp[id][i-1][0];
    }
    //cerr << dp[id][i][0] << ' ';
    for(int k = 1;k <= c.size();k++) {
      if(s[i-1] != 'X') {
	dp[id][i][k] = dp[id][i-1][k];
	if(c[k-1] < i && preWhite[i-1] - preWhite[i-c[k-1]-1] == 0) {
          dp[id][i][k] |= dp[id][i-c[k-1]-1][k-1];
        }
      }  
      //cerr << dp[id][i][k] << ' ';
    }
    //cerr << '\n';
  }
  //cerr << '\n';
}

void buildDp(string s, vector <int> c) {
  computeDp(0, s, c);
  reverse(s.begin(), s.end());
  reverse(c.begin(), c.end());
  //cerr << "scuse me\n";
  computeDp(1, s, c);
}

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

Compilation message (stderr)

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

• 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