Submission #1154403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154403		shadow_sami	Paint By Numbers (IOI16_paint)	C++20	100 / 100	192 ms	85184 KiB

paint

#ifndef LOCAL
	#include "paint.h"
#endif


#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
#define fip(a,b) for(int i = a; i<b; i++)
#define fjp(a,b) for(int j = a; j<b; j++)
#define fp(k,a,b) for(int k = a; k<b; k++)
#define fin(a,b) for(int i = a; i>=b; i--)
#define fjn(a,b) for(int j = a; j>=b; j--)
#define fn(k,a,b) for(int k = a; k>=b; k--)
#define fx(a) for(auto x: a)
#define fy(a) for(auto y: a)
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define test ll t;cin>>t;while(t--)
#define nli "\n"

void _printn(int x){cerr<<x;}
void _printn(ll x){cerr<<x;}
void _printn(float x){cerr<<x;}
void _printn(long double x){cerr<<x<<nli;}
void _printn(double x){cerr<<x<<nli;}
void _printn(char x){cerr<<x<<nli;}
void _printn(string x){cerr<<x<<nli;}
void _printn(bool x){cerr<<x;}
template<class T> void _printn(vector<T> a);
template<class T> void _printn(vector<T> a){cerr<<" ("<<nli;fx(a) cerr<<x<<" "; cerr<<")"<<nli;}

#ifdef LOCAL
	#define debug(x) cerr<<#x<<" ";_printn(x); cerr<<nli;
#else
	#define debug(x)
#endif

ll n,m,res,cnt,ans,sum,tp,tp2,tptp;
bool f = 0;
const ll mod = 1e9 + 7;
const ll mx = 2e5 + 5;
bool dp[mx][105][2];
bool dp2[mx][105][2];
string na;
ll pref[mx];
vi v;

string solve_puzzle(std::string s, std::vector<int> c) {	
	n = s.size();
	s = "#" + s + '#';
	m = c.size();
	v.clear();
	v.push_back(0);
	fx(c)
		v.push_back(x);	
	v.push_back(0);
	fip(0,n+2){
		fjp(0,m+2){
			dp[i][j][0] = dp[i][j][1] = 0;
			dp2[i][j][0] = dp2[i][j][1] = 0;
		}
		pref[i] = 0;
	}
	fip(1,n+1)
		pref[i] = pref[i-1] + (s[i]=='_');	
	dp[0][0][0] = 1;
	fip(1,n+1){
		fjp(0,m+1){			
			dp[i][j][0] = ((dp[i-1][j][0]||dp[i-1][j][1]) && s[i]!='X');
			if(j==0) continue;
			if(i-v[j]<0) continue;						
			tp = i-v[j];
			f = ((pref[i] - pref[tp]) == 0 );
			dp[i][j][1] = (dp[tp][j-1][0] && f);						
			if(dp[i][j][1]){
				debug(i);
				debug(j);
			}
		}
		// cerr<<nli;
	}

	dp2[n+1][m+1][0] = 1;
	fin(n,1){
		fjn(m+1,1){
			dp2[i][j][0] = ((dp2[i+1][j][0]||dp2[i+1][j][1]) && (s[i]!='X'));
			if(j==m+1) continue;
			if(i+v[j]>n+1) continue;
			tp = i + v[j] - 1;
			f = ((pref[tp] - pref[i-1]) == 0 );
			dp2[i][j][1] = (dp2[tp+1][j+1][0] && f);
			if(dp2[i][j][1]){
				debug(i);
				debug(j);
			}
		}
		// cerr<<nli;
	}
	fip(1,n+1){
		cnt = 0;
		fjp(0,m+1)
			if(dp[i][j][0] && dp2[i][j+1][0])
				cnt++;
		if(!cnt)
			s[i] = 'X';
	}	
	fip(0,n+1)
		pref[i] = 0;
	fip(1,n+1){		
		fjp(1,m+1){
			if(i-v[j]>=0 && dp[i][j][1] && dp2[i-v[j]+1][j][1]){				
				tp = i;
				pref[i+1] += -1;
				pref[i-v[j]+1] += 1;
				debug(i);
				debug(j);
				debug(i+1);
				debug(i-v[j]+1);				
			}				
		}
	}		
	string nas;
	fip(1,n+1){
		pref[i] += pref[i-1];		
		if(s[i]=='.')
			if(pref[i]>0)
				s[i] = '?';
			else
				s[i] = '_';
		nas.push_back(s[i]);
	}
	return nas;
}

#ifdef LOCAL
	int main(){
		ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
		#ifdef LOCAL
			freopen("input1.txt","r",stdin);
			freopen("output1.txt","w",stdout);
		#endif
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());	

			string ss;
			cin>>ss;
			int N;
			cin>>N;
			vector<int> c(N);
			fip(0,N)cin>>c[i];
			cout<<solve_puzzle(ss,c)<<nli;
		
		cerr<<"Time elapsed :"<<setprecision(6)<<clock()*1000.0/CLOCKS_PER_SEC<<nli;
		return 0;
	}
#endif

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