Submission #419860

#	Time	Username	Problem	Language	Result	Execution time	Memory
419860		Blagojce	Paint By Numbers (IOI16_paint)	C++11	90 / 100	104 ms	120928 KiB

paint

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5e3 + 3;
 
#include "paint.h"

#include <cstdlib>


int n;
int k;


bool emp[mxn][mxn];
bool exs[mxn][mxn];


bool dp1[mxn][mxn];
bool dp2[mxn][mxn];

bool DP1[mxn][mxn];
bool DP2[mxn][mxn];


int aux1[mxn];
int aux2[mxn];


std::string solve_puzzle(std::string s, std::vector<int> c){
	n = (int)s.size();
	k = (int)c.size();
	fr(i, 0, n){
		fr(j, i, n){
			if(s[j] == 'X') break;
			emp[i][j] = true;
		}
		fr(j, i, n){
			if(s[j] == '_') break;
			exs[i][j] = true;
		}
	}
	
	
	fr(i, 0, n){
		fr(j, 0, k){
			if(i-c[j] + 1 >= 0 && exs[i-c[j]+1][i]){
				if(j == 0){
					if(i-c[j] < 0 || emp[0][i-c[j]]) dp1[i][j] = true;
				}
				else{
					if(i - c[j] > 0 && s[i-c[j]] != 'X' && DP1[i-c[j]-1][j-1]){
						dp1[i][j] = true;
					}
				}
			}
		}
		fr(j, 0, k){
			DP1[i][j] = dp1[i][j];
		}
		if(s[i] != 'X' && i > 0){
			fr(j, 0, k){
				DP1[i][j] |= DP1[i-1][j];
			}
		}
		
	}
	
	for(int i = n-1; i >= 0; i --){
		for(int j = k-1; j >= 0; j--){
			if(i + c[j] - 1 < n && exs[i][i+c[j]-1]){
				if(j == k-1){
					if(i+c[j]>= n || emp[i+c[j]][n-1]) dp2[i][j] = true;
				}
				else{
					if(i + c[j] + 1 < n && s[i+c[j]] != 'X' && DP2[i+c[j]+1][j+1]){
						dp2[i][j] = true;
					}
				}
			}
		}
		
		fr(j, 0, k){
			DP2[i][j] = dp2[i][j];
		}
		if(s[i] != 'X' && i + 1 < n){
			fr(j, 0, k){
				DP2[i][j] |= DP2[i+1][j];
			}
		}
		
		
	}
	

	


	
	fr(i, 0, n){
		fr(j, 0, k){
			bool t1 = dp1[i][j];
			bool t2 = true;
			if(i + 1 < n) t2 = emp[i+1][n-1];
			
			if(j+1< k){
				t2 = false;
				if(i + 2 < n && s[i+1] != 'X'){
					t2 = DP2[i+2][j+1];
				}
			}
			if(t1 && t2){
				aux1[i-c[j]+1] ++;
				aux1[i+1] --;
			}
		}
	}
	for(int i = n-1; i >= 0; i--){
		fr(j, 0, k){
			bool t1 = dp2[i][j];
			bool t2 = true;
			if(i > 0) t2 = emp[0][i-1];
			
			if(j-1>=0){
				t2 = false;
				if(i-2>=0 && s[i-1] != 'X'){
					t2 = DP1[i-2][j-1];
				}
			}
			if(t1 && t2){
				aux1[i] ++;
				aux1[i+c[j]]--;
			}
			
		}
	}
	
	fr(i, 0, n){
		if(s[i] == 'X') continue;
		
		fr(j, -1, k){
			bool lef = emp[0][i];
			
			
			if(j > -1){
				lef = false;
				if(i > 0 && DP1[i-1][j]){
					lef = true;
				} 
			}
			bool rig = emp[i][n-1];
			if(j+1<k){
				rig = false;
				if(i+1<n && DP2[i+1][j+1]){
					rig = true;
				}
			}
			if(lef && rig){
				aux2[i] ++;
				aux2[i+1] --;
				break;
			}
		}
	}
	
	string ans = s;
	
	int sum1 = 0;
	int sum2 = 0;
	fr(i, 0, n){
		sum1 += aux1[i];
		sum2 += aux2[i];
		
		if(s[i] != '.') continue;
		
		if(sum1 && sum2) ans[i] = '?';
		else if(sum1) ans[i] = 'X';
		else ans[i] = '_';
		
	}
	return ans;
}
/*
int main(){
	cout<<solve_puzzle("...........__..........._._._......._.............._.XX.XX.........X.X.XX.X..._..", {2, 6, 8});

}
???????????__???????????_____???????_??????????????_?XX?XX????_____XXXXXXXX______
???????????__???????????_____???????_??????????????_?XX?XX?????????X?XXXXXX??____

*/

• 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: 0 / 10