Submission #672520

#	Time	Username	Problem	Language	Result	Execution time	Memory
672520		Trisanu_Das	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	212 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
 
string solve_puzzle(string s, vector<int> c) {
	int n = s.size(), k = c.size();
	auto check=[&]{
      int pref1[n + 1], pref2[n + 1];
      for(int i = 0; i < n; i++){
        pref1[i + 1] = pref1[i] + (s[i] == '_');
        pref2[i + 1] = pref2[i] + (s[i] == 'X');
      }
      int dp[k + 1][n + 1];
      dp[0][0] = 1;
      for(int i = 0; i < k; i++){
        for(int j = 0; j < n; j++){
          if(j + 1 < c[i]) continue;
          for(int l = -1; l < j; l++){
            if(l > j - c[i]) break;
            if((l >= 0 && l == j - c[i]) || (pref1[j + 1] - pref1[j + 1 - c[i]] > 0 || pref2[j + 1 - c[i]] - pref2[l + 1] > 0)) continue;
            dp[i + 1][j + 1] |= dp[i][l + 1];
          }
          if(i + 1 == k && dp[i + 1][j + 1]) if(pref2[n] - pref2[j + 1] == 0) return true;
        }
      }
      return false;
  };
  string ans = s;
  for(int i = 0;i < n; i++){
		if(s[i] == '_' || s[i] == 'X') continue;
		s[i] = '_';
		int f1 = check();
		s[i] = 'X';
		int f2 = check();
		s[i] = '.';
		if(f1 && f2) ans[i]='?';
		else if(f1) ans[i]='_';
		else if(f2) ans[i]='X';
	}
  return ans;
}

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