Submission #425194

#	Time	Username	Problem	Language	Result	Execution time	Memory
425194		vanic	Paint By Numbers (IOI16_paint)	C++14	100 / 100	287 ms	84752 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

const int maxn=2e5+5, maxk=105;

bool dp[maxn][maxk][2];
bool dp2[maxn][maxk][2];
int n, k;
int sw[maxn];
bool bijela[maxn], crna[maxn];

string solve_puzzle(string s, vector < int > c) {
	n=s.size();
	k=c.size();
	dp[0][0][0]=1;
	int zadnji=0;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=k; j++){
			if(s[i-1]=='_'){
				zadnji=i;
				if(j){
					dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j-1][1];
				}
				else{
					dp[i][j][0]=dp[i-1][j][0];
				}
			}
			else if(s[i-1]=='X'){
				if(j<k && i-zadnji>=c[j]){
					dp[i][j][1]=dp[i-c[j]][j][0];
				}
			}
			else{
				if(j){
					dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j-1][1];
				}
				else{
					dp[i][j][0]=dp[i-1][j][0];
				}
				if(j<k && i-zadnji>=c[j]){
					dp[i][j][1]=dp[i-c[j]][j][0];
				}
			}
		}
	}
	zadnji=n;
	dp2[n][k][0]=1;
	for(int i=n-1; i>=0; i--){
		for(int j=0; j<=k; j++){
			if(s[i]=='_'){
				zadnji=i;
				if(j<k){
					dp2[i][j][0]=dp2[i+1][j][0]+dp2[i+1][j+1][1];
				}
				else{
					dp2[i][j][0]=dp2[i+1][j][0];
				}
				
			}
			else if(s[i]=='X'){
				if(j && zadnji-i>=c[j-1]){
					dp2[i][j][1]=dp2[i+c[j-1]][j][0];
				}
			}
			else{
				if(j<k){
					dp2[i][j][0]=dp2[i+1][j][0]+dp2[i+1][j+1][1];
				}
				else{
					dp2[i][j][0]=dp2[i+1][j][0];
				}
				if(j && zadnji-i>=c[j-1]){
					dp2[i][j][1]=dp2[i+c[j-1]][j][0];
				}
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=0; j<=k; j++){
			
/*			if(i==2 && j==1){
				cout << dp[i][j][0] << ' ' << dp2[i-1][j][0] << endl;
			}*/
			if(dp[i][j][0] && dp2[i-1][j][0]){
				bijela[i-1]=1;
			}
			if(dp[i][j][1] && dp2[i][j+1][0]){
//				cout << "usao " << i << ' ' << j << endl;
//				cout << "usao " << i << ' ' << j << endl;
				sw[i]--;
				sw[i-c[j]]++;
			}
		}
	}
	int uk=0;
	for(int i=0; i<n; i++){
		uk+=sw[i];
		crna[i]=uk;
	}
	string sol;
	for(int i=0; i<n; i++){
		if(bijela[i] && crna[i]){
			sol.push_back('?');
		}
		else if(bijela[i]){
			sol.push_back('_');
		}
		else if(crna[i]){
			sol.push_back('X');
		}
		else{
			sol.push_back('?');
		}
	}
	return sol;
}

• 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