제출 #1223467

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

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=2e5+5,K=1e2+5;

int n,k;
bool dpL[N][K],dpR[N][K];
bool canW[N],canB[N];
int white[N],black[N];
string s;
vector<int>c;

int getW(int l,int r){
	return white[r]-white[l-1];
}
int getB(int l,int r){
	return black[r]-black[l-1];
}

string solve_puzzle(string S,vector<int>C){
	n=S.size(),k=C.size();
	s=" ";
	s+=S;
	c.pb(0);
	c.insert(c.end(),all(C));
	white[0]=black[0]=0;
	for(int i=1;i<=n;i++){
		white[i]=white[i-1]+(s[i]=='_'?1:0);
		black[i]=black[i-1]+(s[i]=='X'?1:0);
	}
	dpL[0][0]=true;
	for(int i=1;i<=n;i++){
		if(getB(1,i)==0){
			dpL[i][0]=true;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(s[i]=='_'){
				dpL[i][j]=dpL[i-1][j];
			}
			else if(s[i]=='X'){
				// i-c[j]+1 , i black
				// i-c[j] white
				if(1<=i-c[j]+1&&getW(i-c[j]+1,i)==0){
					if(i-c[j]==0){
						if(j==1) dpL[i][j]=true;
					}
					else if(s[i-c[j]]!='X'){
						dpL[i][j]=dpL[i-c[j]-1][j-1];
					}
				}
			}
			else{
				bool ok=false;
				if(dpL[i-1][j]==true) ok|=true;
				if(1<=i-c[j]+1&&getW(i-c[j]+1,i)==0){
					if(i-c[j]==0){
						if(j==1) ok|=true;
					}
					else if(s[i-c[j]]!='X'){
						ok|=dpL[i-c[j]-1][j-1];
					}
				}
				dpL[i][j]=ok;
			}
		}
	}
	// for(int i=0;i<=n+1;i++){
	// 	for(int j=0;j<=k+1;j++){
	// 		cerr<<dpL[i][j]<<' ';
	// 	}
	// 	cerr<<"\n";
	// }
	// cout<<"\n";
	dpR[n+1][k+1]=true;
	for(int i=n;i>=1;i--){
		if(getB(i,n)==0){
			dpR[i][k+1]=true;
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=k;j>=1;j--){
			if(s[i]=='_'){
				dpR[i][j]=dpR[i+1][j];
			}
			else if(s[i]=='X'){
				// i , i+c[j]-1 black
				// i+c[j] white
				if(i+c[j]-1<=n&&getW(i,i+c[j]-1)==0){
					if(i+c[j]==n+1){
						if(j==k) dpR[i][j]=true;
					}
					else if(s[i+c[j]]!='X'){
						dpR[i][j]=dpR[i+c[j]+1][j+1];
					}
				}
			}
			else{
				bool ok=false;
				if(dpR[i+1][j]==true) ok|=true;
				if(i+c[j]-1<=n&&getW(i,i+c[j]-1)==0){
					if(i+c[j]==n+1){
						if(j==k) ok|=true;
					}
					else if(s[i+c[j]]!='X'){
						ok|=dpR[i+c[j]+1][j+1];
					}
				}
				dpR[i][j]=ok;
			}
		}
	}
	// for(int i=0;i<=n+1;i++){
	// 	for(int j=0;j<=k+1;j++){
	// 		cerr<<dpR[i][j]<<' ';
	// 	}
	// 	cerr<<"\n";
	// }
	for(int i=1;i<=n;i++){
		canW[i]=false;
		for(int j=0;j<=k;j++){
			if(dpL[i-1][j]==true&&dpR[i+1][j+1]==true){
				canW[i]=true;
				// cerr<<"pos : "<<i<<' '<<j<<' '<<j+1<<"\n";
			}
		}
	}
	vector<int>add(N),sub(N);
	int cur=0;
	for(int j=1;j<=k;j++){
		for(int l=1,r=c[j];r<=n;l++,r++){
			if(getW(l,r)!=0) continue;
			if(l-1>=1&&s[l-1]=='X') continue;
			if(r+1<=n&&s[r+1]=='X') continue;
			if(l==1&&j>1) continue;
			if(l>1&&dpL[l-2][j-1]==false) continue;
			if(r==n&&j<k) continue;
			if(r<n&&dpR[r+2][j+1]==false) continue;
			add[l]++;
			sub[r]++;
			// cerr<<"+ "<<j<<' '<<l<<' '<<r<<"\n";
		}
	}
	for(int i=1;i<=n;i++){
		canB[i]=false;
		cur+=add[i];
		if(cur>0) canB[i]=true;
		cur-=sub[i];
	}
	string ans(n,'.');
	for(int i=1;i<=n;i++){
		if(s[i]!='.') ans[i-1]=s[i];
		else{
			if(canW[i]&&canB[i]) ans[i-1]='?';
			else if(canW[i]) ans[i-1]='_';
			else if(canB[i]) ans[i-1]='X';
		}
	}
	return ans;
}

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