Submission #420053

#	Time	Username	Problem	Language	Result	Execution time	Memory
420053		errorgorn	Paint By Numbers (IOI16_paint)	C++17	100 / 100	298 ms	44996 KiB

paint

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "paint.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());


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

int pd[200005];
int ax[200005];

bool f[200005][105];
bool b[200005][105];

bool blank[200005];
int cx[200005];

std::string solve_puzzle(std::string S, std::vector<int> C) {
    s=S,arr=C;
    n=sz(s),k=sz(arr);
    
    rep(x,0,n){
		if (s[x]=='X') ax[x+1]=1;
		else if (s[x]=='_') pd[x+1]=1;
	}
	
	rep(x,1,n+1) pd[x]+=pd[x-1];
	
	f[0][0]=true;
	rep(x,1,n+1){
		if (ax[x]) continue;
		
		rep(y,0,k){
			f[x][y]|=f[x-1][y];
			if (x-arr[y]-1>=0 && f[x-arr[y]-1][y] && pd[x-1]-pd[x-arr[y]-1]==0) f[x][y+1]=true;
		}
		f[x][k]|=f[x-1][k];
	}
	
	b[n+1][k]=true;
	rep(x,n+1,1){
		if (ax[x]) continue;
		
		rep(y,k,0){
			b[x][y+1]|=b[x+1][y+1];
			if (x+arr[y]+1<=n+1 && b[x+arr[y]+1][y+1] && pd[x+arr[y]]-pd[x]==0) b[x][y]=true;
		}
		b[x][0]|=b[x+1][0];
	}
	
	
	rep(x,1,n+1) rep(y,0,k+1) if (f[x][y] && b[x][y]) blank[x]=true;
	
	rep(x,0,n+1) rep(y,0,k){
		int nxt=x+arr[y];
		if (nxt+1<=n+1 && f[x][y] && b[nxt+1][y+1] && pd[nxt]-pd[x]==0) cx[x+1]++,cx[nxt+1]--;
	}
	
	rep(x,1,n+1) cx[x]+=cx[x-1];
	
	//rep(x,1,n+1) cout<<blank[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<cx[x]<<" "; cout<<endl;
	
	string ans;
	
	rep(x,1,n+1){
		if (blank[x] && cx[x]) ans+="?";
		else if (blank[x]) ans+="_";
		else ans+="X";
	}
	
	return ans;
}

• 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