Submission #117515

#	Time	Username	Problem	Language	Result	Execution time	Memory
117515		nvmdava	Paint By Numbers (IOI16_paint)	C++17	100 / 100	387 ms	50216 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
bool pos[105][200005];
int st[200005], lst[3][200005];
vector<int> cc;
int ans[200005];
bool proc[105][200005];

void solve(int n, int k){
   if(proc[k][n]) return;
   proc[k][n] = 1;
   if(n == 0) return;
   if(st[n] == 2){
      ans[n] |= 2;
      solve(n - 1, k);
   } else if(st[n] == 1){
      for(int j = cc[k - 1] - 1; j >= 0; j--){
         ans[n - j] |= 1;
      }
      ans[n - cc[k - 1]] |= 2;
      solve(n - cc[k - 1] - 1, k - 1);
   } else {
      if(pos[k][n - 1]){
         ans[n] |= 2;
         solve(n - 1, k);
      }
      if(k && lst[2][n] <= n - cc[k - 1] && st[n - cc[k - 1]] != 1 && (n - cc[k - 1] == 0 ? k == 1 : pos[k - 1][n - cc[k - 1] - 1])){
         for(int j = cc[k - 1] - 1; j >= 0; j--){
            ans[n - j] |= 1;
         }
         ans[n - cc[k - 1]] |= 2;
         solve(n - cc[k - 1] - 1, k - 1);
      }
   }
}
string solve_puzzle(string s, vector<int> c) {
   int n = s.size(), k = c.size();
   cc = c;
   pos[0][0] = 1;
   st[0] = 2;
   for(int i = 1; i <= n; i++){
      if(s[i - 1] == '_') st[i] = 2;
      else if(s[i - 1] == 'X') st[i] = 1;

      for(int j = 0; j < 3; j++)
         lst[j][i] = lst[j][i - 1];
      lst[st[i]][i] = i;

      if(st[i] != 1)
         for(int j = 0; j <= k; j++)
            pos[j][i] |= pos[j][i - 1];
      if(st[i] != 2)
         for(int j = 1; j <= k; j++)
            if(lst[2][i] <= i - c[j - 1] && st[i - c[j - 1]] != 1)
               if(i - c[j - 1] == 0)
                  pos[j][i] = j == 1;
               else
                  pos[j][i] |= pos[j - 1][i - c[j - 1] - 1];

   }

   solve(n, k);

   for(int i = 1; i <= n; i++){
      if(ans[i] == 3) s[i - 1] = '?';
      else if(ans[i] == 2) s[i - 1] = '_';
      else s[i - 1] = 'X';
   }
   return s;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:55:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(lst[2][i] <= i - c[j - 1] && st[i - c[j - 1]] != 1)
               ^

• 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