Submission #963296

#	Time	Username	Problem	Language	Result	Execution time	Memory
963296		hyakup	Paint By Numbers (IOI16_paint)	C++17	100 / 100	182 ms	47004 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 2e5 + 20;
const int maxk = 110;

bool dp1[maxn][maxk], dp2[maxn][maxk];
vector<int> sum( maxn );

void pre_calcula( string& s, vector<int>& c ){
  for( int i = 1; i < (int)s.size(); i++ ) sum[i] = sum[i - 1] + ((s[i] == '_') ? 1 : 0 );
  dp1[0][0] = dp2[(int)s.size()][(int)c.size() - 1] = true;
  for( int i = 1; i < (int)s.size() - 1; i++ ){
    for( int j = 0; j < (int)c.size() - 1; j++ ){
      if( s[i] != 'X' ) dp1[i][j] |= dp1[i - 1][j];
      if( i - c[j] - 1 >= 0 && sum[i] - sum[i - c[j]] == 0 && s[i - c[j]] != 'X' ) dp1[i][j] |= dp1[i - c[j] - 1][j - 1];
    }
  }
  for( int i = (int)s.size() - 1; i > 0; i-- ){
    for( int j = (int)c.size() - 1; j > 0; j-- ){
      if( s[i] != 'X' ) dp2[i][j] |= dp2[i + 1][j];
      if( i + c[j] + 1 <= (int)s.size() && sum[i + c[j] - 1] - sum[i - 1] == 0 && s[i + c[j]] != 'X' ) dp2[i][j] |= dp2[i + c[j] + 1][j + 1];
    }
  }
}

void converte( string& s, vector<int>& c ){
  reverse(s.begin(), s.end()); s.push_back('_'); s.push_back('_');
  reverse(s.begin(), s.end()); s.push_back('_'); s.push_back('_');
  reverse(c.begin(), c.end()); c.push_back(maxn); reverse( c.begin(), c.end() ); c.push_back(maxn);
}

string solve_puzzle( string s, vector<int> c ) {
  converte( s, c );
  pre_calcula( s, c );
  vector<int> com((int)s.size()), sem((int)s.size());
  for( int i = 2; i < (int)s.size() - 2; i++ ){
    for( int j = 0; j < (int)c.size() - 1; j++ ){
      if( s[i] != 'X' && dp1[i - 1][j] && dp2[i + 1][j + 1] ) sem[i] = 1;
      if( i + c[j] + 1 <= (int)s.size() ){
        if( sum[i + c[j] - 1] - sum[i - 1] == 0 && s[i - 1] != 'X' && s[i + c[j]] != 'X' && dp1[i - 2][j - 1] && dp2[i + c[j] + 1][j + 1] ){ com[i]++; com[i + c[j]]--; }
      }
    }

    if( s[i] == '_' ) sem[i] = 1;
    if( s[i] == 'X'){ com[i]++; com[i + 1]--; }
  }
  for( int i = 1; i < com.size(); i++ ) com[i] += com[i - 1];
  string resp;
  for( int i = 2; i < s.size() - 2; i++ ){
    if( com[i] && sem[i] ) resp.push_back('?');
    else if( com[i] ) resp.push_back('X');
    else resp.push_back('_');
  }
  return resp;
}

// int main(){
//   string s; cin >> s;
//   int k; cin >> k;
//   vector<int> c;
//   while( k-- ){ int x; cin >> x; c.push_back(x); }
//   cout << solve_puzzle( s, c ) << endl;
// }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for( int i = 1; i < com.size(); i++ ) com[i] += com[i - 1];
      |                   ~~^~~~~~~~~~~~
paint.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for( int i = 2; i < s.size() - 2; i++ ){
      |                   ~~^~~~~~~~~~~~~~

• 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