Submission #314946

#	Time	Username	Problem	Language	Result	Execution time	Memory
314946		nafis_shifat	Paint By Numbers (IOI16_paint)	C++14	100 / 100	218 ms	83824 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5;
const int mxk=103;
const int inf=1e9;
bool dp1[mxn][mxk][2] = {} ,dp2[mxn][mxk][2] = {};

string solve_puzzle(string s, vector<int> c) {
	int n = s.size();
	int k = c.size();
    s = '#' + s;
    c.insert(c.begin(),0);

    int lw = 0;   
    dp1[0][0][0] = true;
    dp2[n+1][k+1][0] = true;
   
	for(int i = 1 ; i <= n; i++) {
		if(s[i] != 'X') {
			dp1[i][0][0] = dp1[i-1][0][0];
			for(int j = 1; j <=k; j++) {
				dp1[i][j][0] = dp1[i-1][j][0] || ((lw <= i - c[j] - 1) && dp1[i - c[j] - 1][j - 1][0]);

			}
		}
		if(s[i] != '_') {
			for(int j = 1; j <= k; j++) {
				dp1[i][j][1] = (i - c[j] >= lw) && dp1[i - c[j]][j - 1][0];
			}
		} else {
			lw = i;
		}
	}

	
	int rw = n + 1;

	for(int i = n ; i >= 1; i--) {
		if(s[i] != 'X') {
			dp2[i][k+1][0] = dp2[i+1][k+1][0];
			for(int j = 1; j <=k; j++) {
				dp2[i][j][0] = dp2[i+1][j][0] || ((rw >= i + c[j] + 1) && dp2[i + c[j] + 1][j + 1][0]);

			}
		}
		if(s[i] != '_') {
			for(int j = 1; j <= k; j++) {
				dp2[i][j][1] = (i + c[j] <= rw) && dp2[i + c[j]][j + 1][0];
			}
		} else {
			rw = i;
		}
	}


	//cout<<dp2[11][3][0]<<" --- "<<dp1[10][2][0]<<endl;

	int t1[n+1] = {};
	int t2[n+1] = {};




	for(int i = 1; i <= n; i++) {
		int mx = -1;
		for(int j = 1; j <= k; j++) {
			if(dp1[i][j][0] && (dp2[i][j+1][0] || dp2[i+1][j+1][1])) t1[i] = 1;
			if(dp1[i][j][1] && dp2[i+1][j+1][0]) mx = max(mx,c[j]);
		}
		if(dp1[i][0][0] && (dp2[i+1][1][0] || dp2[i+1][1][1])) t1[i] = 1;

		for(int j = i; j > i - mx; j--) t2[j] = 1;
	}


    string res = "";
    for(int i = 1; i <= n; i++) {
    	if(t1[i] && t2[i]) res+='?';
    	else if(t1[i]) res+='_';
    	else res+='X';
    }


    return res;
}

• 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