Submission #170525

#	Time	Username	Problem	Language	Result	Execution time	Memory
170525		AlexLuchianov	Paint By Numbers (IOI16_paint)	C++14	100 / 100	497 ms	17264 KiB

paint

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

int const nmax = 200000;
int const cluesmax = 100;

std::bitset<1 + cluesmax> dp[1 + nmax][2];
std::bitset<1 + cluesmax> dp2[1 + nmax][2];

int white[1 + nmax], black[1 + nmax];

int getsum(int x, int y){
  if(0 == x)
    return white[y];
  else
    return white[y] - white[x - 1];
}

int canbeblack[1 + nmax], canbewhite[1 + nmax];

std::string solve_puzzle(std::string s, std::vector<int> clue) {
  int n = s.size();
  std::vector<int> clue2;
  clue2.push_back(0);
  for(int i = 0; i < clue.size(); i++)
    clue2.push_back(clue[i]);
  clue = clue2;

  s = "#" + s;
  dp[0][0][0] = 1;
  for(int i = 1;i <= n; i++) {
    white[i] = white[i - 1] + (s[i] == '_');
    black[i] = black[i - 1] + (s[i] == 'X');
  }

  for(int i = 1;i <= n; i++){
    for(int j = 0;j < clue.size(); j++){
      if(s[i] != 'X')
        dp[i][0][j] = (dp[i - 1][0][j] | dp[i - 1][1][j]);

      if(0 < j && 1 <= i - clue[j] + 1 && getsum(i - clue[j] + 1, i) == 0)
        dp[i][1][j] = (dp[i - clue[j]][0][j - 1]);
    }
  }
  dp2[n + 1][0][clue.size()] = 1;

  for(int i = n; 1 <= i; i--)
    for(int j = 0; j <= clue.size(); j++){
      if(s[i] != 'X')
        dp2[i][0][j] = (dp2[i + 1][0][j] | dp2[i + 1][1][j]);

      if(0 < j && j < clue.size() && i + clue[j] - 1 <= n && getsum(i, i + clue[j] - 1) == 0)
        dp2[i][1][j] = (dp2[i + clue[j]][0][j + 1]);
    }

  for(int i = 1;i <= n; i++) {
    for(int j = 0; j < clue.size(); j++){
      if(dp[i][1][j] == 1 && dp2[i + 1][0][j + 1]) {
        //std::cout << i << " " << j << '\n';
        canbeblack[i - clue[j] + 1]++;
        canbeblack[i + 1]--;
      }
      if(dp[i][0][j] == 1 && (dp2[i + 1][0][j + 1] | dp2[i + 1][1][j + 1]) == 1)
        canbewhite[i]++;
    }
  }
  for(int i = 1; i <= n; i++)
    canbeblack[i] += canbeblack[i - 1];

  std::string result;
  for(int i = 1;i <= n; i++)
    if(canbewhite[i] == 0)
      result += 'X';
    else if(canbeblack[i] == 0)
      result += '_';
    else
      result += '?';
  return result;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < clue.size(); i++)
                  ~~^~~~~~~~~~~~~
paint.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < clue.size(); j++){
                   ~~^~~~~~~~~~~~~
paint.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j <= clue.size(); j++){
                    ~~^~~~~~~~~~~~~~
paint.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(0 < j && j < clue.size() && i + clue[j] - 1 <= n && getsum(i, i + clue[j] - 1) == 0)
                   ~~^~~~~~~~~~~~~
paint.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < clue.size(); j++){
                    ~~^~~~~~~~~~~~~

• 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