Submission #1326306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326306		AMnu	Paint By Numbers (IOI16_paint)	C++20	100 / 100	102 ms	8428 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+5, MAXK = 1e2+5;

int N, K, last, da[MAXN];
string ans;
bitset <MAXK> pre[MAXN], suf[MAXN];

string solve_puzzle(string s,vector<int> c) {
	N = s.size()+1;
	K = c.size();
	s = "__"+s+"__";
	suf[N+1][K] = 1;
	suf[N+2][K] = 1;
	last = N+1;
	for (int i=N;i>1;i--) {
		if (s[i] != 'X') {
			suf[i] = suf[i+1];
		}
		if (s[i] != '_') {
			for (int j=0;j<K;j++) {
				if (i+c[j] <= last && s[i+c[j]] != 'X' && suf[i+c[j]+1][j+1]) {
					suf[i][j] = 1;
				}
			}
		}
		else {
			last = i;
		}
	}
	pre[0][0] = 1;
	pre[1][0] = 1;
	last = 1;
	for (int i=2;i<=N;i++) {
		if (s[i] != 'X') {
			pre[i] = pre[i-1];
		}
		if (s[i] != '_') {
			for (int j=0;j<K;j++) {
				if (i-c[j] >= last && s[i-c[j]] != 'X' && pre[i-c[j]-1][j]) {
					pre[i][j+1] = 1;
					if (s[i+1] != 'X' && suf[i+2][j+1]) {
						da[i-c[j]]++;
						da[i]--;
					}
				}
			}
		}
		else {
			last = i;
		}
		if (s[i] != 'X' && (pre[i-1]&suf[i+1]).any()) {
			ans += '?';
		}
		else {
			ans += 'X';
		}
	}
	for (int i=1;i<N;i++) {
		da[i] += da[i-1];
		if (!da[i]) {
			ans[i-1] = '_';
		}
	}
	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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10