Submission #730630

#	Time	Username	Problem	Language	Result	Execution time	Memory
730630		sentheta	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	340 KiB

paint

#include "paint.h"
#include <cstdlib>
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 105;
const int K = 105;

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

bool canwh[N], canbl[N];

int prfwh[N], prfbl[N];
int cntwh(int l,int r){
	return (r>0 ? prfwh[r]:0) - (l>0 ? prfwh[l-1]:0);
}
int cntbl(int l,int r){
	return (r>0 ? prfbl[r]:0) - (l>0 ? prfbl[l-1]:0);
}

// dp[t][i][j] = last black if fill position 1..i with blocks 1..c
// t = 0 : prefix
// t = 1 : suffix
int dp[2][N][K];
bool can(int t,int i,int j,bool flg=0){
	if(flg){
		if(i<=0) return j<=0;
		// dp[t][i][j]+1 ... i must white
		return !cntbl(dp[t][i][j]+1, i);
	}

	if(t==0){
		if(i<=0) return j<=0;
		// dp[t][i][j]+1 ... i must white
		return !cntbl(dp[t][i][j]+1, i);
	}
	else{
		if(i>n) return j>k;
		// i ... dp[t][i][j]-1 must white
		return !cntbl(i, dp[t][i][j]-1);
	}
}
bool cn[2][N][K];
bool cnf(int t,int i,int j){
	if(t==0){
		if(i<=0) return j<=0;
		return cn[t][i][j];
	}
	else{
		if(i>n) return j>k;
		return cn[t][i][j];
	}
}


string solve_puzzle(string _s,V<int> _c){
	// s.swap(_s); c.swap(_c);
	n = _s.size(); k = _c.size();
	s = " " + _s + " ";
	c = {0};
	for(int x : _c) c.push_back(x);
	c.push_back(0);

	
	// t=0 prefix, t=1 suffix
	rep(t,0,2){
		// dbg(t);
		// cout << s << nl;
		// cout << "c[] "; for(int x : c) cout << x << " ";
		// cout << nl;

		// build prefix sum
		rep(i,1,n+2) prfbl[i] = prfwh[i] = 0;
		rep(i,1,n+1){
			if(s[i]=='X') prfbl[i] = 1;
			if(s[i]=='_') prfwh[i] = 1;
		}
		prfbl[n+1] = prfwh[n+1] = 1;
		rep(i,1,n+2){
			prfbl[i] += prfbl[i-1];
			prfwh[i] += prfwh[i-1];
		}


		// dp transition
		rep(i,0,N) rep(j,0,K) dp[t][i][j] = n+2;
		dp[t][0][0] = -1;
		rep(i,1,n+1) rep(j,1,k+1){
			dp[t][i][j] = n+1;

			// fill previous
			if(s[i]!='X' && can(t,i-1,j,true)){
				dp[t][i][j] = dp[t][i-1][j];
			}

			// fill here
			if(s[i]!='_' && i>=c[j] && can(t,i-c[j]-1,j-1,true)){
				dp[t][i][j] = i;
			}

		}
		rep(i,0,n+1) rep(j,0,k+1) if(can(t,i,j,true)){
			int ii = t ? n+1-i : i;
			int jj = t ? k+1-j : j;
			cn[t][ii][jj] = 1;

			// cout << ii _ jj << nl;
		}

		// reverse suffix into prefix
		reverse(all(s));
		reverse(all(c));
		if(t){
			// for(int i=1; i<=n+1-i; i++) rep(j,1,k+1){
			// 	swap(dp[t][i][j], dp[t][n+1-i][k+1-j]);
			// }
			for(int i=0; i<=n+1-i; i++) rep(j,0,k+1){
				swap(dp[t][i][j], dp[t][n+1-i][j]);
			}
			rep(i,0,n+1) for(int j=0; j<=k+1-j; j++){
				swap(dp[t][i][j], dp[t][i][k+1-j]);
			}
			rep(i,1,n+1) rep(j,1,k+1) if(dp[t][i][j]!=n+2){
				dp[t][i][j] = n+1 - dp[t][i][j];
			}
		}
		// rep(t,0,2){
		// 	dbg(t);
		// 	rep(i,1,n+1) rep(j,1,k+1) if(can(t,i,j)){
		// 		cout << i _ j << nl;
		// 		dbg(dp[t][i][j]);
		// 		dbg(cntbl(i,dp[t][i][j]));
		// 	}
		// 	cout << nl << nl;
		// }
	}

	// build prefix sum
	rep(i,1,n+2) prfbl[i] = prfwh[i] = 0;
	rep(i,1,n+1){
		if(s[i]=='X') prfbl[i] = 1;
		if(s[i]=='_') prfwh[i] = 1;
	}
	prfbl[n+1] = prfwh[n+1] = 1;
	rep(i,1,n+2){
		prfbl[i] += prfbl[i-1];
		prfwh[i] += prfwh[i-1];
	}

	// check if can white
	rep(i,1,n+1) if(s[i]=='.'){
		// put j blocks to left
		rep(j,0,k+1){
			canwh[i] |= cnf(0,i-1,j) && cnf(1,i+1,j+1);
		}
	}

	// check if can black
	// cout << "BLACK SEGS" << nl;
	rep(j,1,k+1) for(int l=1,r=c[j]; r<=n; l++,r++){
		// if(l==1 && r==3){
		// 	dbg(l-2); dbg(j-1);
		// 	dbg(cnf(0,l-2,j-1));
		// 	dbg(s[l-1]);
		// 	dbg(!cntwh(l,r));
		// 	dbg(s[r+1]);
		// 	dbg(cnf(1,r+2,j+1));
		// }

		if(cnf(0,l-2,j-1) && s[l-1]!='X'
		&& !cntwh(l,r)
		&& s[r+1]!='X' && cnf(1,r+2,j+1)
		){
			// cout << l _ r << nl;
			rep(i,l,r+1) canbl[i] = 1;
		}
	}

	string ans = string(n+1,'T');
	rep(i,1,n+1){
		if(s[i]!='.'){
			ans[i] = s[i];
			continue;
		}

		if(canwh[i] && canbl[i]) ans[i] = '?';
		else if(canwh[i]) ans[i] = '_';
		else if(canbl[i]) ans[i] = 'X';
		// else assert(0);
	}
	return ans.substr(1);
}

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