Submission #1326559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326559		Jawad_Akbar_JJ	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	332 KiB

paint

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<18;
int dp1[N][100], dp2[N][100];
int pre[N], dfa[N];

string solve_puzzle(string s, vector<int> c){
	s = '_' + s + '_';
	c.insert(c.begin(), 1);

	int n = s.size() - 1, k = c.size() - 1;

	for (int i=0;i<=n;i++)
		pre[i] = (i == 0 ? 0 : pre[i-1]) + (s[i] == '_');

	dp1[0][0] = dp2[n][k+1] = 1;
	for (int i=0;i<=n;i++){
		for (int j=k;j>=0;j--){
			if (i)
				dp1[i][j] |= dp1[i-1][j] & (s[i] != 'X');
		}
		
		for (int j=1;j<=k;j++)
			if (i + c[j] < n and pre[i+c[j]] - pre[i] == 0)
				dp1[i+c[j]+1][j] |= dp1[i][j-1];
	}
	
	for (int i=n;i>=0;i--){
		for (int j=k+1;j>=1;j--)
			dp2[i][j] |= dp2[i+1][j] & (s[i] != 'X');
		for (int j=k;j>=1;j--){
			if (i - c[j] > 0 and pre[i-1] - pre[i - c[j] - 1] + (s[i - c[j] - 1] == 'X') == 0){
				dp2[i - c[j] - 1][j] |= dp2[i][j+1];
				
				if (dp2[i][j+1] and dp1[i - c[j] - 1][j - 1])
					dfa[i - c[j]] += 2, dfa[i] -= 2;
			}
		}
	}

	string ans, val = " _X?";
	for (int i=1;i<n;i++){
		dfa[i] += dfa[i-1];
		int num = (!!dfa[i]) * 2;
		for (int j=0;j<=k;j++)
			if (dp1[i][j] and dp2[i][j+1])
				num |= 1;
		ans += val[num];
	}
	return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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