Submission #1208223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208223		ansori	Paint By Numbers (IOI16_paint)	C++20	100 / 100	143 ms	81880 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 2 , M = 102;
bool dp[N][M][2] , pd[N][M][2];
std::string solve_puzzle(std::string s, std::vector<int> c) {
	int n = s.size() , m = c.size() , lst = 0;
 	dp[0][0][0] = 1;
 	dp[0][0][1] = 0;
 	for(int i = 1;i <= n; ++ i){
 		dp[i][0][0] = (dp[i - 1][0][0] & (s[i - 1] != 'X'));
 		dp[i][0][1] = 0;
 		if(s[i - 1] == '_') lst = i;
 		for(int j = 1;j <= m; ++ j){
 			if(s[i - 1] != 'X'){
 				dp[i][j][0] = (dp[i - 1][j][0] | dp[i - 1][j][1]);
 			}
 			if(s[i - 1] != '_'){
 				if(i - c[j - 1] >= lst) dp[i][j][1] = dp[i - c[j - 1]][j - 1][0];
 			}
 			// cout << dp[i][j][0] << ' ' << dp[i][j][1] << ' ';
 		}
 		// cout << '\n';
 	}
 	reverse(c.begin() , c.end());
 	lst = n + 1;
 	pd[n + 1][0][0] = 1;
 	pd[n + 1][0][1] = 0;
 	for(int i = n;i >= 1; -- i){
 		pd[i][0][0] = (pd[i + 1][0][0] & (s[i - 1] != 'X'));
 		pd[i][0][1] = 0;
 		if(s[i - 1] == '_') lst = i;
 		for(int j = 1;j <= m; ++ j){
 			if(s[i - 1] != 'X'){
 				pd[i][j][0] = (pd[i + 1][j][0] | pd[i + 1][j][1]);
 			}
 			if(s[i - 1] != '_'){
 				if(i + c[j - 1] <= lst) pd[i][j][1] = pd[i + c[j - 1]][j - 1][0];
 			}
 		}
 	}
 	reverse(c.begin() , c.end());
 	string ans = s;
 	vector<bool> okw(n , 0) , okb(n , 0);
 	for(int i = 0;i < n; ++ i){
 		for(int j = 0;j <= m; ++ j){
 			okw[i] = (okw[i] | ((dp[i][j][1] | dp[i][j][0]) & (pd[i + 2][m - j][1] | pd[i + 2][m - j][0])));
 		}
 	}
 	vector<int> d(n , 0);
 	vector<int> ps = {n * 3};
 	for(int i = n - 1;i >= 0; -- i) if(s[i] == '_') ps.push_back(i);
 	for(int i = 0;i < n; ++ i){
 		for(int j = 0;j < m; ++ j){
 			if(i + c[j] + 1 > n + 1) continue ;
 			if(dp[i][j][0] and pd[i + c[j] + 1][m - j - 1][0] and i + c[j] - 1 < ps.back()){
 				d[i] ++;
 				d[i + c[j]] --;
 				//cout << i << ' ' << c[j] << ' ';
 			}
 		}
 		if(s[i] == '_') ps.pop_back();
 	}
 	int sm = 0;
 	for(int i = 0;i < n; ++ i){
 		sm += d[i];
 		if(sm > 0) okb[i] = true;
 	}
 	for(int i = 0;i < n; ++ i){
 		if(s[i] != '.') continue ;
 		if(okw[i] and okb[i]) ans[i] = '?';
 		else if(okw[i]) ans[i] = '_';
 		else ans[i] = 'X';
 	}
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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