Submission #401767

#	Time	Username	Problem	Language	Result	Execution time	Memory
401767		peuch	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	308 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;

bool can(std::string s, int tam, int pos){
	bool ret = true;
	if(pos - tam + 1 < 0) return false;
	for(int i = pos - tam + 1; i <= pos; i++)
		ret &= s[i] != '_';
	return ret;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
	int n = s.size();
	int k = c.size();
	vector<int> l(k, 0), r(k, 0);
	vector<bool> w(n, false), b(n, false);
	int fim = 0;
	for(int i = 0; i < k; i++){
		fim += c[i] - 1;
		while(!can(s, c[i], fim)) fim++;
		l[i] = fim;
		fim += 2;
//		printf("%d ", l[i]);
	}
//	printf("\n");
	fim = n - 1;
	for(int i = k - 1; i >= 0; i--){
		while(!can(s, c[i], fim)) fim--;
		r[i] = fim;
		fim -= 1 + c[i];
	}
//	for(int i = 0; i < k; i++)
//		printf("%d ", r[i]);
//	printf("\n");
	vector<int> pb(n, INF);
	for(int i = 0; i < k; i++){
		int left = l[i] - c[i] + 1;
		int right = r[i];
		for(int j = left; j <= right; j++)
			pb[j] = min(pb[j], c[i]);
	}
	
	for(int i = 0; i < n; i++){
		if(s[i] == 'X') continue;
		int id = lower_bound(l.begin(), l.end(), i) - l.begin() - 1;
//		printf("k[%d] = %d\n", i, id);
		if(s[i] == '_' || id == k - 1 || r[id + 1] - c[id + 1] + 1 > i) w[i] = true;
		else w[i] = false; 
	}
	
	for(int i = 0; i < n; i++){
		if(s[i] == 'X') {
			b[i] = true;
			continue;
		}
		if(s[i] == '_') continue;
		int tam = pb[i];
		if(tam == INF) {
			b[i] = false;
			continue;
		}
		bool flag = false;
		for(int j = 0; j < tam; j++)
			flag |= can(s, tam, i + j);
		b[i] = flag;
	}
	
	string ans(n, '?');
	for(int i = 0; i < n; i++){
//		printf("%d %d %d\n", i, b[i] ? 1 : 0, w[i] ? 1 : 0);
		if(!b[i]) ans[i] = '_';
		if(!w[i]) ans[i] = 'X';
	}
		
	
    return ans;
}

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