Submission #1278355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278355		WH8	Paint By Numbers (IOI16_paint)	C++20	100 / 100	1535 ms	363232 KiB

paint

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

int n,k;
string s;
vector<int> c;

int mem[200005][102], psw[200005];
vector<pair<int,int>> rs;
bool w[200005], blk[200005];

int dp(int x, int b){
	//~ cout<<n<<" "<<k<<" "<<x<<" "<<b<<endl;
	if(x >= n){
		if(b != k) return 0;
		else return 1;
	}
	assert(b <= k);
	bool ok=false;
	if(mem[x][b]!=-1)return mem[x][b];
	if(b==k or s[x]=='.' or s[x]=='_'){ // try put white.
		if(s[x]=='X'){ // forced to put white, cannot. 
			return mem[x][b]=0;
		}
		if(dp(x+1, b)){
			ok=true;
			w[x]=1;
		}	
		else if(s[x]=='_')return mem[x][b]=0;
	}
	if(b!=k and (s[x]=='X' or s[x]=='.')){
		if(x+c[b] > n){
			if(s[x]=='X')return mem[x][b]=0;
		}
		else {
			if(psw[min(n-1, x+c[b]-1)]-psw[x] != 0 or (x+c[b]!=n and s[x+c[b]]=='X')){
				if(s[x]=='X')return mem[x][b]=0;
			}
			else if(dp(x+c[b]+1, b+1)){
				w[x+c[b]]=1;
				rs.push_back({x, x+c[b]-1});
				ok=true;
			}
			else if(s[x]=='X') return mem[x][b]=0;
		}
	}
	//~ printf("%d %d, ret %d\n", x, b, ok);
	//~ fflush(stdout);
	return mem[x][b]=ok;
}		

string solve_puzzle(string os, vector<int> oc) {
    swap(s, os), swap(c, oc);
    memset(mem, -1, sizeof mem);
    n=s.size(), k=c.size();
    for(int i=1;i<n;i++){
		psw[i]=psw[i-1]+(s[i]=='_'?1:0);
	}
    assert(dp(0, 0));
    sort(rs.begin(),rs.end());

    int ptr=0;
    //~ for(auto it:rs){
		//~ cout<<it.first <<" "<<it.second<<endl;
	//~ }
    for(int i=0;i<n;i++){
		while(ptr < (int)rs.size() and rs[ptr].second < i)ptr++;
		if(ptr < (int)rs.size() and rs[ptr].first <= i)blk[i]=true;
	}
	string res;
	for(int i=0;i<n;i++){
		if(blk[i] and w[i])res+='?';
		else if (blk[i]) res+='X';
		else if (w[i]) res+='_';
		else res+='B';

	}
	return res;
}

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