QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#772098	#5190. 小 E 爱消除	ffffyc	WA	72ms	71632kb	C++14	4.6kb	2024-11-22 17:01:02	2024-11-22 17:01:02

Judging History

你现在查看的是最新测评结果

[2024-11-22 17:01:02]
评测

测评结果：WA
用时：72ms
内存：71632kb

查看

[2024-11-22 17:01:02]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'A'||ch>'Z') ch=gh();
		return ch;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=50+5,INF=1e9+10;
/*
struct node{
	int c,s,r;
	node(int A=0,int B=0,int C=0){ c=A,s=B,r=C; }
	inline friend node operator+(const node &a,const node &b){ return node(a.c+b.c,a.s+b.s,max(a.r,b.r+a.c)); }
};
*/
inline pii operator+(const pii &a,const pii &b){ return mpr(a.fir+b.fir,max(a.sec,b.sec+a.fir)); } 
inline pii operator*(const pii &a,const pii &b){ return mpr(a.fir+b.fir,a.sec+b.sec); } 
int n,c[N];
pii g[N][N],f[N][N][N][N];
inline void upd(pii &x,pii y){ x=min(x,y); }
inline pii F(int l1,int r1,int l2,int r2){//clear [l_1,r_1] [l_2,r_2]
	pii tp;
	if(l1>r1&&l2>r2) tp=mpr(0,0);//,printf("A ");
//	else if(l1>r1) tp=f[l2][r2][r2+1][r2];//,printf("B %d %d ",g[l2][r2].fir,g[l2][r2].sec);
//	else if(l2>r2) tp=f[l1][r1][r1+1][r1];//,printf("C "); 
	else tp=f[l1][r1][l2][r2];//,printf("D ");
	if(tp.fir) tp=mpr(INF,INF);
//	printf("[%d,%d] [%d,%d] %d %d\n",l1,r1,l2,r2,tp.fir,tp.sec);
	return tp;
}
int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		c[i]=read();
	for(int s=1;s<=n;s++){
		for(int l=1,r=s;r<=n;l++,r++){
			g[l][r]=mpr(INF,INF);
			upd(g[l][r],g[l+1][r]*mpr(1,1));
			upd(g[l][r],g[l][r-1]*mpr(1,1));
//					if(l==1&&r==10) printf("?? %d %d\n",g[l][r].fir,g[l][r].sec);
			for(int k=l+1;k<=r;k++)
				if(c[l]==c[k]){
					for(int p=l+1;p<=k;p++){
						pii tp=mpr(1,1)+F(l+1,p-1,k+1,r)+mpr(-1,1)+g[p][k-1];
						upd(g[l][r],mpr(1,1)+F(l+1,p-1,k+1,r)+mpr(-1,1)+g[p][k-1]);
//						if(l==1&&r==10) printf("%d %d %d %d\n",k,p,tp.fir,tp.sec);
					}
					for(int p=k+1;p<=r;p++){
						pii tp=mpr(1,1)+F(l+1,k-1,p+1,r)+mpr(-1,1)+g[k+1][p];
						upd(g[l][r],mpr(1,1)+F(l+1,k-1,p+1,r)+mpr(-1,1)+g[k+1][p]);
//						if(l==1&&r==10) printf("%d %d %d %d\n",k,p,tp.fir,tp.sec);
					}
//					if(l==1&&r==10) printf("A %d %d %d\n",k,g[l][r].fir,g[l][r].sec);
				}
			for(int k=l;k<=r-1;k++)
				if(c[r]==c[k]){
					for(int p=k;p<=r-1;p++){
						pii tp=mpr(1,1)+F(l,k-1,p+1,r-1)+mpr(-1,1)+g[k+1][p];
						upd(g[l][r],mpr(1,1)+F(l,k-1,p+1,r-1)+mpr(-1,1)+g[k+1][p]);
//						if(l==1&&r==10) printf("%d %d %d %d %d %d\n",k,p,tp.fir,tp.sec,F(l,k-1,p+1,r-1).fir,F(l,k-1,p+1,r-1).sec);
					}
					for(int p=l;p<=k-1;p++){
						pii tp=mpr(1,1)+F(l,p-1,k+1,r-1)+mpr(-1,1)+g[p][k-1];
						upd(g[l][r],mpr(1,1)+F(l,p-1,k+1,r-1)+mpr(-1,1)+g[p][k-1]);
//						if(l==1&&r==10) printf("%d %d %d %d %d %d\n",k,p,tp.fir,tp.sec,F(l,p-1,k+1,r-1).fir,F(l,p-1,k+1,r-1).sec);
					}
//					if(l==1&&r==10) printf("B %d %d %d\n",k,g[l][r].fir,g[l][r].sec);
				}
//			printf("[%d,%d] %d %d\n",l,r,g[l][r].fir,g[l][r].sec);
		}
		for(int len1=0,len2=s;len2>=0;len1++,len2--)
			for(int l1=1,r1=len1;r1<=n;l1++,r1++)
				for(int l2=r1+1,r2=l2+len2-1;r2<=n;l2++,r2++){
					f[l1][r1][l2][r2]=mpr(INF,INF);
					if(r1-l1+r2-l2&1) continue; 
					for(int p=l1+1;p<=r1;p++)
						if(c[l1]==c[p])
							for(int q=l2;q<=r2+1;q++)
								upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1+1,p-1,q,r2)+mpr(-1,1)+F(p+1,r1,l2,q-1));
					for(int q=l2;q<=r2;q++)
						if(c[l1]==c[q])
							for(int p=l1;p<=r1;p++)
								upd(f[l1][r1][l2][r2],mpr(1,1)+F(l1+1,p,q+1,r2)+mpr(-1,1)+F(p+1,r1,l2,q-1));
					if(!len1){
						for(int q=l2;q<=r2;q++)
							if(c[r2]==c[q])
								upd(f[l1][r1][l2][r2],mpr(1,1)+F(1,0,q+1,r2)+mpr(-1,1)+F(1,0,l2,q-1));
					}
//					if(f[l1][r1][l2][r2].fir>=INF) continue;
				}
	}
	write(g[1][n].fir),putc(' '),write(g[1][n].sec);
	flush();
}
/*
50
50 34 43 39 50 21 50 27 34 7 50 2 7 27 2 43 21 43 7 7 39 34 7 32 50 34 50 34 32 34 32 34 21 27 7 2 50 34 27 39 39 7 21 21 7 27 39 50 34 7
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 72ms

memory: 71632kb

input:

50
14 31 14 31 14 31 14 14 14 31 14 14 14 31 31 31 14 31 31 31 31 14 31 14 31 14 31 14 31 31 14 31 14 14 31 31 14 31 31 14 14 31 31 14 31 31 14 14 31 14

output:

0 3

result:

ok single line: '0 3'

Test #2:

score: -100

Wrong Answer

time: 42ms

memory: 71232kb

input:

50
1 18 18 18 50 1 50 1 18 18 50 18 18 18 50 1 50 1 18 50 18 50 50 50 18 18 18 50 50 1 18 18 18 18 50 1 50 1 50 50 18 1 50 50 50 1 1 18 18 50

output:

2 4

result:

wrong answer 1st lines differ - expected: '2 3', found: '2 4'