Submission #127746

#	Time	Username	Problem	Language	Result	Execution time	Memory
127746		mirbek01	Paint By Numbers (IOI16_paint)	C++11	32 / 100	3 ms	632 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

int pref[3][N], dp[105][N], f[4][N], n, m;

string solve_puzzle(string s, vector<int> c) {
      n = (int)s.size();
      m = (int)c.size();
      s = ' ' + s;
      string ans;

      for(int i = 1; i <= n; i ++){
            if(s[i] == '_')
                  pref[1][i] ++;
            if(s[i] == 'X')
                  pref[2][i] ++;
            pref[1][i] += pref[1][i - 1];
            pref[2][i] += pref[2][i - 1];
      }

      for(int i = c[0]; i <= n; i ++){
            int wh = pref[1][i] - pref[1][i - c[0]];
            if(!wh && !pref[2][i - c[0]])
                  dp[0][i] = 1;
            dp[0][i] += dp[0][i - 1];
      }

      int sum = c[0] + 1;

      for(int i = 1; i < m; i ++){
            for(int j = c[i] + sum; j <= n; j ++){
                  int lo = 1, hi = j - c[i] - 1;
                  while(lo <= hi){
                        int md = (lo + hi) >> 1;
                        int bl = pref[2][j - c[i] - 1] - pref[2][md - 1];
                        if(!bl)
                              hi = md - 1;
                        else
                              lo = md + 1;
                  }
                  int can = dp[i - 1][j - 1] - dp[i - 1][hi];
                  if(can)
                        dp[i][j] = 1;
                  dp[i][j] += dp[i][j - 1];
            }
            sum += c[i] + 1;
      }

      int pt = 1;

      for(int i = 0; i < m; i ++){
            while(dp[i][pt] - dp[i][pt - 1] == 0)
                  pt ++;
            f[0][pt - c[i] + 1] ++;
            f[0][pt + 1] --;
            pt ++;
      }

      for(int i = 1; i <= n; i ++)
            f[0][i] += f[0][i - 1];

      for(int i = 1; i <= n; i ++){
            if(!f[0][i])
                  f[1][i] = 1;
      }

      int lst = n;

      for(int i = m - 1; i >= 0; i --){
            bool ok = 1;
            int l;
            for(int j = lst; j >= 1; j --){
                  if(dp[i][j] - dp[i][j - 1]){
                        f[2][j - c[i] + 1] ++;
                        f[2][j + 1] --;
                        if(ok){
                              f[3][j - c[i] + 1] --;
                              lst = j - c[i] - 1;
                              ok = 0;
                        }
                        l = j - c[i] + 1;
                  }
            }
            f[3][l] ++;
      }

      for(int i = 1; i <= n; i ++){
            f[2][i] += f[2][i - 1];
            f[3][i] += f[3][i - 1];
            if(f[2][i])
                  f[0][i] = 1;
            if(f[3][i])
                  f[1][i] = 1;
      }

      for(int i = 1; i <= n; i ++){
            if(f[0][i] && f[1][i])
                  ans += '?';
            else if(f[0][i])
                  ans += 'X';
            else
                  ans += '_';
      }

      return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:89:19: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
             f[3][l] ++;
             ~~~~~~^

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