Submission #958001

#	Time	Username	Problem	Language	Result	Execution time	Memory
958001		Lalic	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2064 ms	3484 KiB

paint

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int memo[2][MAXN];

int is_pos(string s, vector<int>& c){
	int n=(int)s.size(), k=(int)c.size();
	vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
	
	bool ok=0;
	int lastW=-1;
	for(int i=0;i<n;i++){
		if(s[i]=='_') lastW=i;
		
		if(i && s[i]!='X'){
			for(int j=0;j<=k;j++)
				dp[i][j]=dp[i-1][j];
		}
		else if(s[i]=='X') ok=1;
		
		if(ok) dp[i][0]=0;
		else dp[i][0]=1;
		
		for(int j=1;j<=k;j++){
			if(i+1<c[j-1] || i-lastW<c[j-1] || (i-c[j-1]>=0 && s[i-c[j-1]]=='X') || (i<n-1 && s[i+1]=='X')) continue;
			if(i-c[j-1]-1<0){
				if(j==1) dp[i][j]=i+1;
				else dp[i][j]=0;
			}
			else if(dp[i-c[j-1]-1][j-1]) dp[i][j]=i+1;
		}
	}
	
	if(dp[n-1][k]){
		int ptr=n-1, qnt=k;
		while(qnt){
			int aux=dp[ptr][qnt];
			
			while(ptr>=aux){
				memo[0][ptr]=1;
				ptr--;
			}
			for(int i=0;i<c[qnt-1];i++){
				memo[1][ptr]=1;
				ptr--;
			}
			if(ptr>=0) memo[0][ptr]=1;
			ptr--;
			
			qnt--;
		}
	}
	
	return dp[n-1][k];
}

string solve_puzzle(string s, vector<int> c) {
    string ans="";
    memset(memo, 0, sizeof memo);
    
    for(int i=0;i<(int)s.size();i++){
		if(s[i]!='.') ans+=s[i];
		else{
			s[i]='X';
			int bl;
			if(memo[1][i]) bl=1;
			else bl=is_pos(s, c);
			
			s[i]='_';
			int wh;
			if(memo[0][i]) wh=1;
			else wh=is_pos(s, c);

			if(bl && wh) ans+='?';
			else if(bl) ans+='X';
			else ans+='_';
			
			s[i]='.';
		}
	}
		
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10