Submission #33228502

---

Source Code Expand

#include<cmath>
#include<vector>
#include<string>
#define cmin(x,y) if(x>y) x=y;
#define cmax(x,y) if(x<y) x=y;
#define eb emplace_back
using namespace std;
using db=double;
using uni=unsigned long long;
const int FSIZE=1<<26,INF=0x7fffffff,fx[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
const db pi=acos(-1);
struct image{
	int rx,ry;
	vector<vector<bool>> raw,null,vis;
	image(const char *s){
		raw.resize(1);
		for(int i=0;*s=='\n'||*s=='#'||*s=='.';++s)
			if(*s=='\n'){
				if(*(s+1)=='.'||*(s+1)=='#') raw.resize(++i+1);
			}else raw[i].eb(*s=='#');
		ry=raw[0].size();
		null.resize(rx=raw.size());
		for(int i=0;i<rx;++i) null[i].resize(ry);
	}
	image(int x,int y){
		raw.resize(rx=x+1);
		ry=y+1;
		for(int i=0;i<=x;++i) raw[i].resize(y+1);
		null=raw;
	}
	image(int w,const char *s):ry(w){
		int i=0;bool p=0;
		raw.resize(1);
		auto get=[&](int k){
			for(int j=0;j<k;++j){
				raw[i].eb(p);
				if(raw[i].size()==ry) raw.resize(++i+1);
			}
			p^=1;};
		for(uni k=0;*s;++s)
			if(*s==' '){
    			if(k<190) get(k);
    			else for(uni x=k;x;x>>=5) get(x&31);
    			k=0;
			}else k=k*95+*s-33;
		raw.pop_back();
		null.resize(rx=raw.size());
		for(int i=0;i<rx;++i) null[i].resize(ry);
	}
	auto &operator[](int x){return(raw[x]);}
	struct sqr{
		int x0,x1,y0,y1;
		void operator+=(sqr b){
			cmin(x0,b.x0)cmax(x1,b.x1)
			cmin(y0,b.y0)cmax(y1,b.y1)
		}
		void operator+=(pair<int,int> b){
			cmin(x0,b.first)cmax(x1,b.first)
			cmin(y0,b.second)cmax(y1,b.second)
		}
	};
	sqr find(int x,int y){
		sqr re={x,x,y,y};
		vis[x][y]=1;
		for(int i=0,nx,ny;i<8;++i)
			if(~(nx=x+fx[i][0])&&~(ny=y+fx[i][1])&&nx<rx&&ny<ry&&!vis[nx][ny]&&raw[nx][ny]==raw[x][y])
				re+=find(nx,ny);
		return(re);
	}
	template<class T>void foreach(T func){
		for(int i=0;i<rx;++i)
			for(int j=0;j<ry;++j) func(i,j);
	}
	auto &reno(){
		vis=null;
		foreach([&](int x,int y){
			int bk=raw[x][y];
			for(int i=0,nx,ny;i<8;++i)
				if(~(nx=x+fx[i][0])&&~(ny=y+fx[i][1])&&nx<rx&&ny<ry)
					bk+=raw[nx][ny];
			raw[x][y]=bk>4;});
		return(*this);
	}
	auto split(){
		vector<image> re;
		vis=null;
		for(int i=0;i<ry;++i)
			for(int j=0,nx,ny;j<rx;++j)
				if(raw[j][i]&&!vis[j][i]){
					sqr out=find(j,i);
					if((nx=out.x1-out.x0)*(ny=out.y1-out.y0)<80) continue;
					image nxt(nx,ny);
					for(int x=0;x<=nx;++x)
						for(int y=0;y<=ny;++y)
							nxt[x][y]=raw[x+out.x0][y+out.y0];
					re.eb(nxt);
				}
		return(re);
	}
	template<class T>auto trans(T func){
		vector<pair<int,int>> point;
		sqr out={INF,-INF,INF,-INF};
		foreach([&](int x,int y){
			if(!raw[x][y]) return;
			auto p=func(x,y);
			point.eb(p);
			out+=p;});
		image re(out.x1-out.x0,out.y1-out.y0);
		for(auto i:point)
			re[i.first-out.x0][i.second-out.y0]=1;
		return(re);
	}
	auto rotate(db ang){
		ang=ang/180*pi;
		db csa=cos(ang),sia=sin(ang),cex=rx/2.,cey=ry/2.;
		return(trans([&](int x,int y){
			return(make_pair((x-cex)*csa+(y-cey)*sia+cex,-(x-cex)*sia+(y-cey)*csa+cey));}));
	}
	auto cut(db cx,db cy){
		return(trans([&](int x,int y){return(make_pair(x+y*cy,y+x*cx));}));
	}
	auto fit(int rxt,int ryt){
		image re(rxt,ryt);
		db delx=(db)rxt/rx,dely=(db)ryt/ry;
		foreach([&](int x,int y){if(raw[x][y]) re[x=x*delx][y=y*dely]=1;});
		return(re);
	}
	db match(image &x){
		if(min(abs((db)ry/rx-(db)x.ry/x.rx),abs((db)rx/ry-(db)x.rx/x.ry))>0.2) return(0);
		int re=0,mix=min(rx,x.rx)-1,miy=min(ry,x.ry)-1;
		auto a=this->fit(mix,miy),b=x.fit(mix,miy);
		a.foreach([&](int x,int y){re+=a[x][y]==b[x][y];});
		return((db)re/(mix*miy));
	}
};
vector<image> trans[16];
vector<image> charset({
{30,"/(Z>k5rpG- 05|Tes`Cbl %.)|F7>Tu5 oo3$s$lNM oo3$s/)(] /iV1d;jA>K 0/t0K-(usu `2O#f.n=G S%2Op3 "},
{27,"4;{D@&Ol^x /xoT%W-H Oe%.AxXC5 Oe%.AxXC5 Oe%.AxXC5 \"ID8yq \"H )j "},
{28,"+Mm-u+r60= 05kx9`fP'\\ (l?:yvmH\\( 4;|B@rIg:# _QwDo9;'' ,[0E@,wQP6 Sh:[IpOZP \"U *+ "},
{28,")cKS}@p1aD 05kx9`@[os Ou2:MXQ0| 9`+Zk=.dpe 0lBpTs;8Fp 0)zxq3Q?Gt U]FR>4oH. FZf "},
{30,"`\"pAl[\\K# ;U@Xq(T{S6 0;5oU%v}!m ,Ke6O>2pa( #}l8n \"v P6LVwNc`t #4ySB5i,x "},
{28,"-8/eJXT]M8 0l32ni_ecN )c;vg@iA.j 0lR{i<~bGD <PhMqXvpa; 0<5X1fSWr Y);f+{U:* "},
{29,"0lRMbF!8wy 0lRL7Yx_SH ,eb&_jD~Vh 3D!XEg<#NV #>Rj1Z7L*b 1T(FG.o^*z 0vvDh$?P\\d NYT%H` "},
{28,"4t \"M %32,I{nYnJ -C1BZI\"y/ OeEu3c$?{ U/M^Xc}Q> Ou0p'}`{+ Oe&]KK|_d 64j90R$ "},
{28,"+M|;cpYJ[F 00S,13#;^b &|D-U=zs\\? C.=c-%,17 1feVt=l2qQ 7uJ6=&~X}V 3_-]065<>e =DM\"WnRe=Y $. "},
{28,")^1i*Xxot+ 06,/jya!3S 7uEU#Pb}jU 5Nx13cQ{?C 0*,{fU\"MZY 2Vcx.kHhAS 4A6]cbs'j4 qpQpj< "},
{21,"0A$&=F3'Ba 2+U;$UvGD/ 99fCq\"2p_~ 0F=p1!?(*p ;)aRed1r)W 20oUjR3+f* 5jLYN_H`p2 .Va|8bD*3+ $fC1 "},
{21,"3j7^;;Iyw 204P[FOo4 99vP~Sd5*W 0F=p1!f8a> 7J+NR4p][# 20o%s!.]h_ 2+E_4w$-Zf .VaLA1?Q?5 5qqD "},
{27,R"(JKhf2n"v; 0>qwv>q " JKhf2n"l0 "v42HHf&g )"},{28,"4U \"N *+ "},
{26,"J<*z]Vh( &pNR}bx5_b eSZ\\ _ #>1#V6Hu.5 /tF\">9a{Ct 3^N.E-.1}M 7%2 "},
{28,"JL9YFlFi\" JL9Y:!~TT OtaHl7%r OtaHl7%R JL9YFk8F* JL9Y:!~TT Ou27IYGzC OtaHl7%R #z3[eZ "}});
char charname[17]="0123456789()+-*/";
string ans;
int t,n,m;
char BuF[FSIZE],*InF=BuF;
void read(int &x){
	for(;*InF<33;++InF);
	for(x=0;32<*InF;x=x*10+(*InF++^48));
}
void init(){
	for(int i=0;i<16;++i)
		for(db j=-15;j<16;j+=3){
			auto tmp=charset[i].rotate(j).reno();
			trans[i].eb(tmp.cut(-.1,-.1).reno());
			trans[i].eb(tmp.cut(-.1,.1).reno());
			trans[i].eb(tmp.cut(.1,-.1).reno());
			trans[i].eb(tmp.cut(.1,.1).reno());
			trans[i].eb(tmp);
		}
}
#define caseopt(x) case #x[0]:st0.back()x##=rhs;break;
int level(char c){return(c=='('?0:1+(c=='*'||c=='/'));}
int calc(string& s){
	vector<int> st0;
	vector<char> st1;
	int optnum=0,isd=0;
	auto calc=[&](char c){
		int rhs=st0.back();
		st0.pop_back();
		switch(c){
			caseopt(+)
			caseopt(-)
			caseopt(*)
			caseopt(/)
		}
	};
	for(auto &c:s){
		if(47<c&&c<58){
			optnum=10*optnum+(c^48);
			isd=1;
			continue;
		}
		if(isd){
			st0.eb(optnum);
			isd=optnum=0;
		}
		if(st1.size()) switch(c){
			case '(':
				st1.eb(c);
				break;
			case ')':
				for(;st1.back()!='(';st1.pop_back()) calc(st1.back());
				st1.pop_back();
				break;
			default:
				for(;st1.size()&&level(c)<=level(st1.back());st1.pop_back()) calc(st1.back());
				st1.eb(c);
			}
		else st1.eb(c);
	}
	if(47<s.back()&&s.back()<58) st0.eb(optnum);
	for(;st1.size();st1.pop_back()) calc(st1.back());
	return(st0.back());
}
int main(){
	fread(BuF,1,FSIZE,stdin);
	init();
	read(t);read(n);read(m);
	for(;*InF<33;++InF);
	image in(InF);
	for(auto &i:in.reno().split()){
		db bestmatch=0,tmp;int bestnum=0;
		for(int j=0;j<16;++j){
			tmp=i.match(charset[j]);
			if(tmp>0&&tmp<.5) continue;
			for(auto &k:trans[j])
				if((tmp=i.match(k))>bestmatch){
					bestmatch=tmp;
					bestnum=j;
				}
		}
		ans+=charname[bestnum];
	}
	printf("%d\n",calc(ans));
}

Submission Info

Judge Result