QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167179#7106. Infinite Parenthesis SequenceDiwanulWA 172ms3856kbC++142.5kb2023-09-07 11:53:362023-09-07 11:53:37

Judging History

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

  • [2023-09-07 11:53:37]
  • 评测
  • 测评结果:WA
  • 用时:172ms
  • 内存:3856kb
  • [2023-09-07 11:53:36]
  • 提交

answer

//prepare for coding{{{
#include<bits/stdc++.h>

#define RELEASE
#ifdef RELEASE
#define DB(...) ;
#else
#define FL
#ifdef FL
#define DB(...) fprintf(stderr,__VA_ARGS__)
#else
#define DB printf
#endif
#endif 
#define int long long

const int N=100000,Q=100000,LGN=20;
const int INF=1000000000;

using namespace std;

mt19937 Rand(time(0));

inline int Read(){
	char c=getchar();
	int res=0;
	bool b=0;
	while(c>'9'||c<'0')
		b=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')
		res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return b?-res:res;
}

inline void ReadS(int &n,bool a[]){
	char c=getchar();
	while(c!='('&&c!=')')
		c=getchar();
	n=0;
	while(c=='('||c==')')
		a[++n]=(c=='('),c=getchar();
}

inline int Min(int a,int b){
	return a>b?b:a;
}

inline int Mod(int x,int mod){
	return ((x-1)%mod+mod)%mod+1;
}

int n,q;
bool a[N+10];
//}}}

//st table{{{
int mn[LGN+10][N+10],tl;
int lg[N+10];
int bs,dj;

inline void ST(){
	lg[1]=0;
	for(int i=2;i<=tl;++i)
		lg[i]=lg[i>>1]+1;
	for(int i=1,s=2;s<=tl;++i,s<<=1)
		for(int j=1;j+s-1<=tl;++j)
			mn[i][j]=Min(mn[i-1][j],mn[i-1][j+(s>>1)]);
	dj=n-2*tl;
	bs=Min(mn[lg[tl]][1],mn[lg[tl]][tl-(1<<lg[tl])+1]);
}

inline int ST_Min(int l,int r){
	int t=lg[r-l+1];
	return Min(mn[t][l],mn[t][r-(1<<t)+1]);
}

inline int Query(int l,int r){
	int tnl=(l+tl-1>0?(l+tl-1)/tl:l/tl),a=ST_Min(Mod(l,tl),tl)+(tnl-1)*dj;
	int tnr=(r>0?(r-1)/tl:r/tl-1),b=ST_Min(1,Mod(r,tl))+tnr*dj;
	return tnl==tnr+1?ST_Min(Mod(l,tl),Mod(r,tl))+tnr*dj:Min(Min(a,b),tnl==tnr?INF:bs+dj*(dj>0?tnr-1:tnl));
}
//}}}

//solve{{{
inline int Get(int tn,int x){
	return Query(x,x+tn)+x+x+tn;
}

inline int Lower_Bound(int tn,int lim){
	int l=-INF,r=INF-1,ans=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Get(tn,mid)>=lim)
			r=(ans=mid)-1;
		else
			l=mid+1;
	}
	return ans;
}

inline int Upper_Bound(int tn,int lim){
	int l=-INF,r=INF-1,ans=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Get(tn,mid)>lim)
			r=(ans=mid)-1;
		else
			l=mid+1;
	}
	return ans;
}
//}}}

//main{{{
inline void Solve(){
	n=Rand()%100000+1;
	for(int i=1;i<=n;++i)
		putchar(Rand()&1?'(':')');
	printf("\n%d\n",q=100000);
	for(int i=1;i<=q;++i){
		int a=Rand()%(2*INF)-INF,b=Rand()%(2*INF)-INF;
		if(a>b)
			swap(a,b);
		printf("%d %d %d\n",Rand()%INF,a,b);
	}
}

signed main(){
#ifdef FL
	freopen(".in","w",stdout);
#endif
	int T=10;
	printf("%d\n",T);
	++T;
	while(--T)
		Solve();
	return 0;
}
//}}}
//《象》曰:泽灭木,大过。君子以独立不惧,遁世无闷。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 172ms
memory: 3856kb

input:

3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3

output:

10
)()))))((()(()()(())())((())()((())(()(((((((()()(((())()(((()(()())((((())()(()(()()))()(((((()(((()()((())))))())())()(())())))())())(()((()((()))))))(())(())(()((())((()(()()(((()))(()()()(((((()))())))))()())))(((()())))))()())(()()())))()))()(()())((()()))))))(()))))(()((()((()()))())))(())(...

result:

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