Submission #453869

#	Time	Username	Problem	Language	Result	Execution time	Memory
453869		PedroBigMan	Paint By Numbers (IOI16_paint)	C++14	100 / 100	947 ms	142388 KiB

paint

#include "paint.h"
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 500000000LL
#define EPS 0.00000001
#define pi 3.14159
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll PS(vector<ll> *ps, ll l, ll r) 
{
	if(l==0) {return (*ps)[r];} else {return ((*ps)[r]-(*ps)[l-1]);}
}

string solve_puzzle(string s, vector<int> c) 
{
	ll N=s.size(); ll K=c.size();
	if(N==1) {return "X";}
    vector<ll> psU,psB,psW; ll cursumU=0LL,cursumB=0LL,cursumW=0LL;
	REP(i,0,N)
	{
		if(s[i]=='.') {cursumU++;} else if(s[i]=='X') {cursumB++;} else {cursumW++;}
		psU.pb(cursumU); psB.pb(cursumB); psW.pb(cursumW);
	}
	bool dp1[N][K+1],dp2[N][K+1]; REP(i,0,N) {REP(j,0,K+1) {dp1[i][j]=false; dp2[i][j]=false;}}
	// dp1[pos][k]  means you can clear until position pos with c_0,...,c_(k-1). dp2[pos][k] means you can clear after inclusive position pos with c_k,...,c_(K-1)
	REP(i,0,N)
	{
		if(PS(&psB,0,i)==0) {dp1[i][0]=true;} else {dp1[i][0]=false;}
		if(PS(&psB,i,N-1)==0) {dp2[i][K]=true;} else {dp2[i][K]=false;}
	}
	REP(j,2,K+1) {dp1[0][j]=false;}
	REP(j,0,K-2) {dp2[N-1][j]=false;}
	if(c[0]>1 || s[0]=='_') {dp1[0][1]=false;} else {dp1[0][1]=true;}
	if(c[K-1]>1 || s[N-1]=='_') {dp2[N-1][K-1]=false;} else {dp2[N-1][K-1]=true;}
	REP(i,1,N)
	{
		REP(j,1,K+1)
		{
			if(s[i]!='X' && dp1[i-1][j]) {dp1[i][j]=true;}
			else if(j==1 && i+1==c[0] && PS(&psW,0,i)==0) {dp1[i][j]=true;}
			else if(i+1>c[j-1] && PS(&psW,i-c[j-1]+1,i)==0 && s[i-c[j-1]]!='X' && ((i==c[j-1] && j==1) || (i-c[j-1]-1>=0 && dp1[i-c[j-1]-1][j-1]))) {dp1[i][j]=true;}
		}
	}
	for(ll i=N-2;i>=0;i--)
	{
		for(ll j=K-1;j>=0;j--)
		{
			if(s[i]!='X' && dp2[i+1][j]) {dp2[i][j]=true;}
			else if(j==K-1 && N-i==c[K-1] && PS(&psW,i,N-1)==0) {dp2[i][j]=true;}
			else if(N-i>c[j] && PS(&psW,i,i+c[j]-1)==0 && s[i+c[j]]!='X' && ((i+c[j]==N-1 && j==K-1) || (i+c[j]+1<=N-1 && dp2[i+c[j]+1][j+1]))) {dp2[i][j]=true;}
		}
	}
	bool b[N][K]; REP(i,0,N) {REP(j,0,K) {b[i][j]=false;}}
	REP(j,0,K)
	{
		REP(i,0,N-c[j]+1)
		{
			bool ok1=true; 
			if(i-2>=0) {ok1=dp1[i-2][j];} else if(j==0) {ok1=true;} else {ok1=false;}
			bool ok2=true;
			if(i+c[j]+1<N) {ok2=dp2[i+c[j]+1][j+1];} else if(j==K-1) {ok2=true;} else {ok2=false;}
			bool ok3=true;
			if(PS(&psW,i,i+c[j]-1)!=0) {ok3=false;} 
			if(i>0 && s[i-1]=='X') {ok3=false;}
			if(i+c[j]<N && s[i+c[j]]=='X') {ok3=false;}
			if(ok1&&ok2&&ok3) {b[i][j]=true;}
		}
	}
	vector<vector<ll> > psb; vector<ll> xx; REP(i,0,N) {xx.pb(0);} REP(i,0,K) {psb.pb(xx);}
	ll cursum;
	REP(i,0,K) 
	{
		cursum=0;
		REP(j,0,N)
		{
			if(b[j][i]) {cursum++;}
			psb[i][j]=cursum;
		}
	}
	vector<bool> okW; vector<bool> okB; REP(i,0,N) {okW.pb(false); okB.pb(false);}
	REP(i,0,N)
	{
		if(s[i]=='X') {continue;}
		if(i==0) 
		{
			if(dp2[1][0]) {okW[i]=true;}
		}
		else if(i==N-1)
		{
			if(dp1[N-2][K]) {okW[i]=true;}
		}
		else
		{
			REP(j,0,K+1)
			{
				if(dp1[i-1][j] && dp2[i+1][j]) {okW[i]=true;}
			}
		}
	}
	REP(i,0,N)
	{
		if(s[i]=='_') {continue;}
		REP(j,0,K)
		{
			if(PS(&psb[j],max(0,i-c[j]+1),i)!=0) {okB[i]=true;}
		}
	}
	string ans=""; 
	REP(i,0,N) 
	{
		if(okW[i]&&(!okB[i])) {ans+='_';}
		else if((!okW[i])&&okB[i]) {ans+='X';}
		else {ans+='?';}
	} 
	return ans;
}

Compilation message (stderr)

paint.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
paint.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      |

• 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