Submission #1149541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149541		LCJLY	Paint By Numbers (IOI16_paint)	C++20	100 / 100	674 ms	122924 KiB

paint

#include "paint.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int arr[105];
int white[200005];
int black[200005];
int n,k;

int f(int a, int b){
	//can i tile black
	int hold=white[b]-white[a-1];
	if(hold>=1) return 0;
	else return 1;
}

int f2(int a, int b){
	//can i tile white
	int hold=black[b]-black[a-1];
	if(hold>=1) return 0;
	else return 1;
}

int memo[200005][105];

bool dp(int index, int cur){
	if(index>n){
		if(cur==k) return 1;
		else return 0;
	}
	if(memo[index][cur]!=-1) return memo[index][cur];
	
	bool ans=false;
	
	//white
	if(f2(index,index)){
		ans|=dp(index+1,cur);
	}
	
	//black
	if(cur<k&&index+arr[cur]<=n&&f(index,index+arr[cur]-1)&&f2(index+arr[cur],index+arr[cur])){
		ans|=dp(index+arr[cur]+1,cur+1);
	}
	
	return memo[index][cur]=ans;
}

bool visited[200005][105];
int black2[200005];
int white2[200005];

void dfs(int index, int cur){
	if(index>n) return;
	if(visited[index][cur]) return;
	visited[index][cur]=true;
	
	if(f2(index,index)&&memo[index+1][cur]==1){
		dfs(index+1,cur);
		white2[index]++;
		white2[index+1]--;
	}
	
	if(cur<k&&index+arr[cur]<=n&&f(index,index+arr[cur]-1)&&f2(index+arr[cur],index+arr[cur])&&memo[index+arr[cur]+1][cur+1]){
		//cout << index << " " << cur << " black\n";
		dfs(index+arr[cur]+1,cur+1);
		black2[index]++;
		black2[index+arr[cur]]--;
		white2[index+arr[cur]]++;
		white2[index+arr[cur]+1]--;
	}
}


string solve_puzzle(string s, vector<int> c) {
	
	k=c.size();
    
    for(int x=0;x<k;x++){
		arr[x]=c[x];
	}
	
	s=" "+s;
	n=s.length();
	
	for(int x=1;x<n;x++){
		white[x]=white[x-1];
		black[x]=black[x-1];
		
		if(s[x]=='X') black[x]++;
		else if(s[x]=='_') white[x]++;
		//cout << black[x] << " " << white[x] << "\n";
	}
	
	memset(memo,-1,sizeof(memo));
	dp(1,0);
	
	//backtrack
	
	dfs(1,0);
	
	string ans="";
	for(int x=1;x<n;x++){
		white2[x]+=white2[x-1];
		black2[x]+=black2[x-1];
		if(white2[x]>0&&black2[x]>0) ans+='?';
		else if(white2[x]>0) ans+='_';
		else ans+='X'; 
	}
	
	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