제출 #206648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206648		kshitij_sodani	Paint By Numbers (IOI16_paint)	C++17	59 / 100	5 ms	380 KiB

paint

#include <iostream>
#include <bits/stdc++.h>
#include <paint.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long llo;
#define a first
#define  b second
#define endl "\n"
string solve_puzzle(string s,vector<int> c){
	int k=c.size();
	int n=s.size();
	char ss[n];
	strcpy(ss,s.c_str());
	int it[n];
	for(int i=0;i<n;i++){
		if(ss[i]=='.'){
			it[i]=0;
		}
		else if(ss[i]=='_'){
			it[i]=1;
		}
		else{
			it[i]=2;
		}
	}
	vector<pair<int,int>> seg;
	int st=0;
	for(int i=0;i<n;i++){
		if(st==0 and it[i]==0){
			st=1;
			seg.pb(mp(i,i));
		}
		else{
			if(it[i]==0){
				seg[seg.size()-1].b+=1;
			}
			else{
				st=0;
			}
		}
	}
	/*for(int i=0;i<seg.size();i++){
		cout<<seg[i].a<<" "<<seg[i].b<<endl;
	}*/
	int ind2=0;
	int ind3=0;
	pair<pair<int,int>,pair<int,int>> ind[n];
	for(int i=0;i<k;i++){
		ind3=max(ind3,seg[ind2].a);
		while(seg[ind2].b-ind3+1<c[i]){
			ind2+=1;
			ind3=max(ind3,seg[ind2].a);
		}
		ind[i].a=mp(ind2,ind3);
	//	cout<<ind2<<" "<<ind3<<" "<<i<<endl;
		ind3+=c[i]+1;

	}
	ind2=seg.size()-1;
	ind3=n-1;
	for(int i=k-1;i>=0;i--){
		ind3=min(ind3,seg[ind2].b);
		while(ind3-seg[ind2].a+1<c[i]){
			ind2-=1;
			ind3=min(ind3,seg[ind2].b);
		}
		ind[i].b=mp(ind2,ind3);

	//	cout<<ind2<<" "<<ind3<<" "<<i<<endl;
		ind3-=c[i]+1;
	}

	int fill[n];
	memset(fill,0,sizeof(fill));
	char ans[n];
	for(int i=0;i<n;i++){
		ans[i]=ss[i];
		if(ans[i]=='.'){
			ans[i]='?';
		}
	}

	for(int i=0;i<k;i++){
		int fill2[n];
		memset(fill2,0,sizeof(fill2));
		if(ind[i].a.a==ind[i].b.a){
			for(int j=ind[i].a.b;j<ind[i].a.b+c[i];j++){
				fill2[j]+=1;
			//	cout<<j<<" ";
			}
			for(int j=ind[i].b.b;j>ind[i].b.b-c[i];j--){
				fill2[j]+=1;
				//cout<<j<<" ";
				if(fill2[j]==2){
					ans[j]='X';
	//				cout<<j<<",";
				}
			}
	//		cout<<endl;
		}
		for(int j=ind[i].a.a+1;j<ind[i].b.a;j++){
			if(seg[j].b-seg[j].a+1>=c[i]){
				for(int ii=seg[j].a;ii<seg[j].b+1;ii++){
					fill[ii]+=1;
				}
			}
		}
		for(int j=ind[i].a.b;j<min(seg[ind[i].a.a].b+1,ind[i].b.b+1);j++){
			fill[j]+=1;
	//		cout<<j<<":";
		}
	//	cout<<endl;
		for(int j=ind[i].b.b;j>=max(seg[ind[i].b.a].a,ind[i].a.b);j--){
			fill[j]+=1;
	//		cout<<j<<":";
		}
	//	cout<<endl;


	}
	for(int i=0;i<n;i++){
		if(fill[i]==0){
			ans[i]='_';
		}
	}
	string ans2="";
	for(int i=0;i<n;i++){
		ans2+=ans[i];
	}
	return ans2;
}
/*int main(){
	vector<int> bb={2,3};
	cout<<solve_puzzle("..._..._....", {3,4});

	return 0;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10