Submission #1183688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183688		Nonoze	Paint By Numbers (IOI16_paint)	C++20	7 / 100	0 ms	328 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second

int n, k;
vector<int> pref0, pref1;

int nb0(int l, int r) {
	if (l>r) return 0;
	return pref0[r]-(l==0?0:pref0[l-1]);
}

int nb1(int l, int r) {
	if (l>r) return 0;
	return pref1[r]-(l==0?0:pref1[l-1]);
}

string solve_puzzle(string s, vector<int> c) {
	n=sz(s), k=sz(c);
	for (int i=0; i<n; i++) {
		if (i) pref0.pb(pref0.back()), pref1.pb(pref1.back());
		else pref0.pb(0), pref1.pb(0);
		if (s[i]=='X') pref1.back()++;
		else if (s[i]=='_') pref0.back()++;
	}
	vector<vector<bool>> dpl(n+2, vector<bool>(k+1, 0)), dpr=dpl, okl=dpl, okr=dpl;
	for (int i=0; i<=n+1; i++) dpr[i][k]=1;
	for (int i=n-1; i>=0; i--) {
		for (int j=0; j<k; j++) {
			if (s[i]!='X') dpr[i][j]=dpr[i+1][j];
			if (i+c[j]-1<n && nb0(i, i+c[j]-1)==0 && (i==0 || s[i-1]!='X') && (i+c[j]==n || s[i+c[j]]!='X') && dpr[i+c[j]+1][j+1]) {
				dpr[i][j]=okr[i][j]=1;
			}
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<k; j++) {
			if (i && s[i]!='X') dpl[i][j]=dpl[i-1][j];
			if (i-c[j]+1>=0 && nb0(i-c[j]+1, i)==0 && (i==n-1 || s[i+1]!='X') && (i-c[j]==-1 || s[i-c[j]]!='X') && (!j || (i-c[j]-1>=0 && dpl[i-c[j]-1][j-1]))) {
				dpl[i][j]=okl[i][j]=1;
			}
		}
	}
	int end=-1;
	for (int i=0; i<n; i++) {
		bool one=nb1(0, i-1)==0&&okr[i][0];
		if (one) end=max(end, i+c[0]-1);
		if (i<=end) one=1;
		for (int j=0; j<k; j++) {
			if (i>=2 && dpl[i-2][j] && okr[i][j+1]) {
				one=1;
				end=max(end, i+c[j]-1);
			}
			if (okl[i][j] && dpr[i+2][j+1]) {
				one=1;
			}
		}
		bool zero=nb1(0, i-1)==0&&dpr[i+1][0];
		for (int j=0; j<k; j++) {
			if (i>=1 && dpl[i-1][j] && dpr[i+1][j+1]) {
				zero=1;
				break;
			}
		}
		if (s[i]=='.') {
			if (zero && one) s[i]='?';
			else if (zero) s[i]='_';
			else if (one) s[i]='X';
		}
	}
	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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10