Submission #117520

#	Time	Username	Problem	Language	Result	Execution time	Memory
117520		nvmdava	Paint By Numbers (IOI16_paint)	C++17	100 / 100	595 ms	168824 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#define N 200005

int q[N], o[3][N], p[105][N], w[105][N], r[N];
vector<int> y;

void solve(int n, int k){
   if(p[k][n] || !n) return;
   p[k][n] = 1;
   if(q[n] == 2){
      r[n] |= 2;
      solve(n - 1, k);
   } else if(q[n] == 1){
      for(int j = y[k - 1] - 1; j >= 0; j--){
         r[n - j] |= 1;
      }
      r[n - y[k - 1]] |= 2;
      solve(n - y[k - 1] - 1, k - 1);
   } else {
      if(w[k][n - 1]){
         r[n] |= 2;
         solve(n - 1, k);
      }
      if(k && o[2][n] <= n - y[k - 1] && q[n - y[k - 1]] != 1 && (n - y[k - 1] == 0 ? k == 1 : w[k - 1][n - y[k - 1] - 1])){
         for(int j = y[k - 1] - 1; j >= 0; j--){
            r[n - j] |= 1;
         }
         r[n - y[k - 1]] |= 2;
         solve(n - y[k - 1] - 1, k - 1);
      }
   }
}
string solve_puzzle(string s, vector<int> c) {
   int n = s.size(), k = c.size(), i, j;
   y = c;
   w[0][0] = 1;
   q[0] = 2;
   for(i = 1; i <= n; i++){
      if(s[i - 1] == '_') q[i] = 2;
      else if(s[i - 1] == 'X') q[i] = 1;

      for(j = 0; j < 3; j++)
         o[j][i] = o[j][i - 1];
      o[q[i]][i] = i;

      if(q[i] != 1)
         for(j = 0; j <= k; j++)
            w[j][i] |= w[j][i - 1];
      if(q[i] != 2)
         for(j = 1; j <= k; j++)
            if(o[2][i] <= i - c[j - 1] && q[i - c[j - 1]] != 1)
               if(i - c[j - 1] == 0)
                  w[j][i] = j == 1;
               else
                  w[j][i] |= w[j - 1][i - c[j - 1] - 1];

   }

   solve(n, k);

   for(i = 1; i <= n; i++){
      if(r[i] == 3) s[i - 1] = '?';
      else if(r[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:52:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
             if(o[2][i] <= i - c[j - 1] && q[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