제출 #779140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
779140		vjudge1	Paint By Numbers (IOI16_paint)	C++17	90 / 100	1250 ms	242532 KiB

paint

#include<bits/stdc++.h> 
#include "paint.h"
using namespace std;
const int N=5e3+37;
int dp[N][N][2], dp2[N][N][2];
int check1[N];

void check(string s, vector<int> c){
	int p=0;
	int k=c.size(); int n= s.size();

	for(auto i: c){
		p+=i;
		check1[p] = 1;
	}

	if(s[0]!='X') dp[0][0][0] = 1;
	if(s[0] != '_') dp[0][1][1] = 1;


	for(int i=1; i<n; i++){
		for(int l=0; l<=n; l++){
			if(dp[i-1][l][0]){
				if(s[i]!='X') dp[i][l][0] = 1;
				if(s[i]!='_') dp[i][l+1][1] = 1;
			}
			if(dp[i-1][l][1]){
				if(check1[l]&&s[i]!='X') dp[i][l][0] = 1;
				else if(!check1[l]&&s[i]!='_') dp[i][l+1][1] = 1;
			}
		}
	}

	for(int i=0; i<=n; i++) check1[i]=0;

	int f=0;
	p++;
	for(int l=k-1; l>=0; l--){
		f+=c[l];

		check1[p-f] = 1;

	}
	p--;
	//cout<<p;
	if(s[n-1]!='X') dp2[n-1][p][0] = 1;
	if(s[n-1] != '_') dp2[n-1][p][1] = 1;

	for(int i=n-2; i>=0; i--){
		for(int l=0; l<=n; l++){
			if(dp2[i+1][l][0]){
				if(s[i]!='X') dp2[i][l][0] = 1;
				if(s[i]!='_') dp2[i][l][1] = 1;
			}
			if(dp2[i+1][l][1]){
				if(check1[l]&&s[i]!='X'){
				 	
				 	dp2[i][l-1][0]=1;
				 	
				 }
				else if(!check1[l]&&s[i]!='_') dp2[i][l-1][1] = 1;
			}
		}
	}


}	
std::string solve_puzzle(std::string s, std::vector<int> c) {
   
	string t, ans;
	int n=s.size();
	int k=c.size();
	check(s, c);

	ans=s;
	for(int i=0; i<=n; i++) check1[i] =0;
	check1[c[0]] = 1;
	check1[0] = 1;
	for(int i=1; i<c.size(); i++){
		c[i]+=c[i-1];
	}
	for(int i=0; i<n; i++){
		if(s[i]!='.') continue;

		int b=0, w=0;
		for(int l=0; l<=n; l++){

			if(dp[i][l][1] && dp2[i][l][1])
			{
				b = 1;
			}
			if(dp[i][l][0] && dp2[i][l][0]){
				w = 1;
			}
		}

		if(b&&w) ans[i] = '?';
		else if(b) ans[i] ='X';
		else if(w) ans[i]='_';

	}
	//cout<<ans;
	return ans;
}	
/*

int main() {

    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    string s; cin >> s;

     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);

    // BEGIN SECRET
 //   puts("098d134608c94f7413faac591054ee35");
    // END SECRET

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

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=1; i<c.size(); i++){
      |               ~^~~~~~~~~
paint.cpp:72:6: warning: unused variable 'k' [-Wunused-variable]
   72 |  int k=c.size();
      |      ^

• 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