제출 #475902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475902		AdamGS	Paint By Numbers (IOI16_paint)	C++14	100 / 100	595 ms	171172 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, MAXK=107;
int pref[LIM][MAXK], suf[LIM][MAXK], lewo[LIM], prawo[LIM], sum[LIM];
string solve_puzzle(string s, vector<int>c) {
	int n=s.size(), k=c.size();
	pref[0][0]=1;
	rep(i, n) {
		if(s[i]!='X') {
			rep(j, k+1) pref[i+1][j]=pref[i][j];
		}
		if(s[i]!='_') {
			lewo[i+1]=lewo[i]+1;
			rep(j, k) {
				if(lewo[i+1]>=c[j]) {
					if(i-c[j]+1==0) {
						if(j==0) pref[i+1][j+1]=1;
					} else if(s[i-c[j]]!='X' && pref[i-c[j]][j]) {
						pref[i+1][j+1]=1;
					}
				}
			}
		}
	}
	suf[n+1][k+1]=1;
	for(int i=n-1; i>=0; --i) {
		if(s[i]!='X') {
			rep(j, k+1) suf[i+1][j+1]=suf[i+2][j+1];
		}
		if(s[i]!='_') {
			prawo[i+1]=prawo[i+2]+1;
			rep(j, k) {
				if(prawo[i+1]>=c[j]) {
					if(i+1+c[j]==n+1) {
						if(j==k-1) suf[i+1][j+1]=1;
					} else if(s[i+c[j]]!='X' && suf[i+c[j]+2][j+2]) {
						suf[i+1][j+1]=1;
					}
				}
			}
		}
	}
	rep(i, n) if(s[i]=='.') {
		bool ok=false;
		rep(j, k+1) if(pref[i][j] && suf[i+2][j+1]) ok=true;
		if(!ok) s[i]='X';
	}
	rep(j, k) {
		for(int i=c[j]-1; i<n; ++i) {
			if(lewo[i+1]>=c[j]) {
				bool ok=true;
				if(i+1-c[j]==0 && j>0) ok=false;
				if(i+1-c[j]>0 && (pref[i-c[j]][j]==0 || s[i-c[j]]=='X')) {
					ok=false;
				}
				if(i+1==n && j<k-1) ok=false;
				if(i+1<n && (suf[i+3][j+2]==0 || s[i+1]=='X')) ok=false;
				if(ok) {
					++sum[i-c[j]+1];
					--sum[i+1];
				}
			}
		}
	}
	int akt=0;
	rep(i, n) {
		akt+=sum[i];
		if(s[i]=='.') {
			if(akt==0) s[i]='_';
			else s[i]='?';
		}
	}
	return s;
}

• 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