제출 #1136672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136672		raspy	Paint By Numbers (IOI16_paint)	C++20	100 / 100	249 ms	167200 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

int dpp[200005][105];
int dps[200005][105];
int kum[200005];
int sums[200005];

string solve_puzzle(string s, vector<int> c)
{
	int n = s.size(), k=c.size();
	for (int i = 1; i <= n; i++)
		kum[i]=kum[i-1]+(s[i-1]=='_');
	dpp[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (s[i-1] != 'X') dpp[i][j] |= dpp[i-1][j];
			if (j >= 1 && c[j-1] <= i && kum[i]-kum[max(0, i-c[j-1])] == 0 && (i == c[j-1] || s[i-c[j-1]-1] != 'X'))
				dpp[i][j] |= dpp[max(0, i-c[j-1]-1)][j-1];
		}
	}
	dps[n+1][k+1] = 1;
	for (int i = n; i >= 1; i--)
	{
		for (int j = k+1; j >= 1; j--)
		{
			// if (i == 3)
			// 	cout << "j: " << j << ": " << dps[i+1][j] << "\n";
			if (s[i-1] != 'X') dps[i][j] |= dps[i+1][j];
			if (j <= k && c[j-1]+i <= n+1 && kum[i+c[j-1]-1]-kum[i-1] == 0 && (n-i+1 == c[j-1] || s[i+c[j-1]-1] != 'X'))
			{
				// if (i==7)
				// 	cout << j << ":" << " " << i+c[j-1]+1<< " test\n";
				dps[i][j] |= dps[min(n+1, i+c[j-1]+1)][j+1];
			}
		}
	}
	string rez;
	int cx = 0;
	for (int i = 1; i <= n; i++)
	{
		cx+=sums[i];
		if (s[i-1] != '.')
		{
			rez += s[i-1];
			if (s[i-1] == 'X')
			{
				for (int j = 1; j <= k; j++)
				{
					if (i+c[j-1]-1 <= n && dpp[max(0, i-2)][j-1] && dps[min(n+1, i+c[j-1]+1)][j+1] && kum[min(n, i+c[j-1]-1)]-kum[i-1]==0
						&& (i == 1 || s[max(0, i-2)]!='X') && (i == n || s[min(n, i+c[j-1]-1)] != 'X'))
					{
						cx++;
						sums[i+c[j-1]]--;
					}
				}
			}
			continue;
		}
		int stanje = 0;
		for (int j = 0; j <= k; j++)
		{
			if (dpp[i-1][j] && dps[i+1][j+1])
				stanje|=1;
		}
		for (int j = 1; j <= k; j++)
		{
			if (i+c[j-1]-1 <= n && dpp[max(0, i-2)][j-1] && dps[min(n+1, i+c[j-1]+1)][j+1] && kum[min(n, i+c[j-1]-1)]-kum[i-1]==0
				&& s[max(0, i-2)]!='X' && s[min(n, i+c[j-1]-1)] != 'X')
			{
				cx++;
				sums[i+c[j-1]]--;
			}
		}
		if (cx > 0)
			stanje|=2;
		if (stanje==3) rez+= "?";
		else if (stanje==2)rez+= "X";
		else if (stanje==1) rez+= "_";
		else rez+="t";
	}
	return rez;
}

컴파일 시 표준 에러 (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