Submission #730649

#	Time	Username	Problem	Language	Result	Execution time	Memory
730649		sentheta	Paint By Numbers (IOI16_paint)	C++17	100 / 100	855 ms	65856 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 = 2e5+5;
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[i][j] = last black if fill position 1..i with blocks 1..c
// t = 0 : prefix
// t = 1 : suffix
bool dp[N][K];
bool can(int i,int j){
	if(i<=0) return j<=0;
	return dp[i][j];
	// dp[i][j]+1 ... i must white
	// return !cntbl(dp[i][j]+1, i);
}

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];
	}
}


struct Fenw{
	int fw[N];
	Fenw(){
		rep(i,0,N) fw[i] = 0;
	}
	void upd(int l,int r){
		for(; l<N; l+=l&-l) fw[l]++;
		for(r++; r<N; r+=r&-r) fw[r]--;
	}
	int qry(int i){
		int ret = 0;
		for(; i>0; i-=i&-i) ret += fw[i];
		return ret;
	}
} fenw;

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];
		}


		rep(i,0,N) rep(j,0,K) dp[i][j] = 0;
		rep(i,0,n+1){
			if(s[i]=='X') break;
			dp[i][0] = 1;
		}
		// dp[0][0] = 1;

		// dp transition
		rep(i,1,n+1) rep(j,1,k+1){
			dp[i][j] = 0;

			// empty here
			if(s[i]!='X' && can(i-1,j)){
				dp[i][j] = 1;
			}
			// fill here
			if(s[i]!='_' && i>=c[j] && s[i-c[j]]!='X'
			&& !cntwh(i-c[j]+1,i) && can(i-c[j]-1,j-1)){
				dp[i][j] = 1;
			}
		}
		rep(i,0,n+1) rep(j,0,k+1) if(can(i,j)){
			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));
	}

	// 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;
			fenw.upd(l,r);
			// 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] && fenw.qry(i)) ans[i] = '?';
		// if(canwh[i] && canbl[i]) ans[i] = '?';
		else if(canwh[i]) ans[i] = '_';
		// else if(canbl[i]) ans[i] = 'X';
		else if(fenw.qry(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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10