Submission #705061

#	Time	Username	Problem	Language	Result	Execution time	Memory
705061		esomer	Paint By Numbers (IOI16_paint)	C++17	100 / 100	519 ms	174972 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"

using namespace std;
 
#define endl "\n"
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

string solve_puzzle(string s, vector<int> c){
	int n = (int)s.size();
	int k = (int)c.size();
	vector<vector<int>> left(n, vector<int>(k, 0));
	int mn = n;
	int mx = -1;
	int lst = -1;
	for(int i = 0; i < n; i++){
		if(s[i] == 'X'){mn = min(mn, i); mx = i;}
		if(s[i] != 'X' && i > 0){
			for(int j = 0; j < k; j++){
				if(left[i-1][j] != 0) left[i][j] = 1;
			}
		}
		if(s[i] == '_') {lst = i; continue;}
		for(int j = 0; j < k; j++){
			if(lst >= i - c[j] + 1) continue;
			if(i - c[j] < 0 || s[i - c[j]] != 'X'){
				if(j == 0){
					if(mn > i - c[j]) left[i][j] = 2;
				}else if(i - c[j] - 1 >= 0 && left[i - c[j] - 1][j-1] > 0) left[i][j] = 2;
			}
		}
	}
	vector<vector<int>>  right(n, vector<int>(k, 0));
	lst = n;
	vector<int> v;
	for(int i = n - 1; i >= 0; i--){
		if(s[i] != 'X' && i < n - 1){
			for(int j = 0; j < k; j++){
				if(right[i+1][j] != 0) right[i][j] = 1;
			}
		}
		if(s[i] == '_') {v.push_back(i); lst = i; continue;}
		for(int j = 0; j < k; j++){
			if(lst <= i + c[j] - 1) continue;
			if(i + c[j] >= n || s[i + c[j]] != 'X'){
				if(j == k-1){
					if(mx <= i + c[j]) right[i][j] = 2;
				}else if(i + c[j] + 1 < n && right[i + c[j] + 1][j+1] > 0) right[i][j] = 2;
			}
		}
	}
	vector<int> next(n, -1);
	for(int i = 0; i < n; i++){
		if(s[i] == '_') {v.pop_back(); continue;}
		int mex = -1;
		for(int j = 0; j < k; j++){
			if(i + c[j] - 1 >= n || ((int)v.size() > 0 && v.back() <= i + c[j] - 1) || (i > 0 && s[i-1] == 'X') || (i == 0 && j > 0)) continue;
			bool gd = 0;
			if(j == 0){
				if(mn >= i){
					if(k == 1){
						if(i + c[j] >= n || s[i + c[j]] != 'X' && mx <= i + c[j] - 1) gd = 1;
					}else{
						if(i + c[j] + 1 < n && s[i + c[j]] != 'X' && right[i + c[j] + 1][j+1] > 0) gd = 1;
					}
				}
			}else if(j == k - 1){
				if(mx <= i + c[j] - 1){
					if(i - 2 >= 0 && left[i-2][j-1] > 0) gd = 1;
				}
			}else{
				if(i - 2 >= 0 && left[i-2][j-1] > 0 && i + c[j] + 1 < n && s[i + c[j]] != 'X' && right[i + c[j] + 1][j+1] > 0) gd = 1;
			}
			if(gd) mex = max(mex, i + c[j] - 1);
		}
		next[i] = mex;
	}
	vector<int> er(n, 0);
	int curr = 0;
	string ans = s;
	for(int i = 0; i < n; i++){
		if(next[i] != -1){
			curr++;
			er[next[i]]++;
		}
		if(i > 0) curr -= er[i-1];
		if(ans[i] == '.'){
			bool white = 0;
			if((i < n - 1 && right[i+1][0] > 0 && mn > i) || (i > 0 && left[i-1][k-1] > 0 && mx < i)) white = 1;
			if(i > 0 && i < n - 1){
				for(int j = 0; j < k - 1; j++){
					if(left[i-1][j] > 0 && right[i+1][j+1] > 0) white = 1;
				}
			}
			if(!white){
				ans[i] = 'X';
				continue;
			}
			if(curr > 0) ans[i] = '?';
			else ans[i] = '_';
		}
	}
	return ans;
}

//~ const int S_MAX_LEN = 200 * 1000;
//~ char buf[S_MAX_LEN + 1];

//~ int main() {
    //~ assert(1 == scanf("%s", buf));
    //~ std::string s = buf;
    //~ int c_len;
    //~ assert(1 == scanf("%d", &c_len));
    //~ std::vector<int> c(c_len);
    //~ for (int i = 0; i < c_len; i++) {
        //~ assert(1 == scanf("%d", &c[i]));
    //~ }
    //~ std::string ans = solve_puzzle(s, c);


    //~ printf("%s\n", ans.data());
    //~ return 0;
//~ }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:65:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   65 |       if(i + c[j] >= n || s[i + c[j]] != 'X' && mx <= i + c[j] - 1) gd = 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