Submission #1283182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283182		Jawad_Akbar_JJ	Paint By Numbers (IOI16_paint)	C++20	100 / 100	241 ms	167060 KiB

paint

#include <iostream>
#include <vector>
#include "paint.h"
using namespace std;
const int M = 200005;
int pre[M], Pre[M][105], Suf[M][105], cnt[M];
string solve_puzzle(string s, vector<int> c){
	int n = s.size(), k = c.size();
	s = '0' + s;
	s = s + '0';

	for (int i=1;i<=n;i++){
		pre[i] = pre[i-1] + (s[i] == '_');
	}

	Pre[0][0] = 1;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=k;j++){
			if (j < k and Pre[i-1][j] and i + c[j] - 1 <= n and pre[i + c[j] - 1] - pre[i-1] == 0 and s[i + c[j]] != 'X')
				Pre[i+c[j]][j+1] = 1;
			if (s[i] != 'X')
				Pre[i][j] |= Pre[i-1][j];
		}
	}

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

	for (int i=1;i<=n;i++){
		for (int j=0;j<k;j++)
			if (Pre[i-1][j] and i + c[j] - 1 <= n and pre[i + c[j] - 1] - pre[i-1] == 0 and s[i + c[j]] != 'X' and Suf[i + c[j]][j+2])
				cnt[i]++, cnt[i+c[j]]--;
	}

	for (int i=1;i<=n;i++){
		cnt[i] += cnt[i-1];
		char c = s[i];
		for (int j=0;j<=k;j++){
			if (c == '.' and Pre[i][j] and Suf[i][j+1] and cnt[i] > 0)
				s[i] = '?';
			else if (c == '.' and s[i] != '?' and Pre[i][j] and Suf[i][j+1])
				s[i] = '_';
			else if (c == '.' and s[i] != '?' and cnt[i] > 0)
				s[i] = 'X';
		}
	}
	s.erase(begin(s));
	s.erase(prev(end(s)));
	return s;
}

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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10