提交记录 3731


用户 题目 状态 得分 用时 内存 语言 代码长度
ghostfly233 noi18b. 【NOI2018】冒泡排序 Wrong Answer 80 57.112 ms 3940 KB C++ 909 B
提交时间 评测时间
2018-07-18 15:58:10 2020-07-31 21:25:08
#include<cstdio>
#include<cstring>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define Mod 998244353

int n;
int a[600001];

// straight-forward DP
// f[i][j] : [1..i] maximum=j
// f[i][j] -> f[i+1][k](k>j) , f[i+1][j](fill in [minimum+1] && j>i)
// f[i][j] = f[i-1][k](k<j) + f[i-1][j](j>=i)
int f[1001][1001];
int vis[1001];
void solve1(){
	memset(vis,0,sizeof vis);
	memset(f,0,sizeof f);
	int ok=1,oo,maxq=a[1]; vis[a[1]]=1;
	F(j,a[1]+1,n) f[1][j]=1;
	F(i,2,n){
		f[i][i]=(f[i-1][i-1]+f[i-1][i])%Mod;
		F(j,i+1,n) f[i][j]=(f[i][j-1]+f[i-1][j])%Mod;
		oo=1;
		if(a[i]<maxq){
			F(j,1,a[i]-1) if(!vis[j]) {oo=0; break;}
		}
		else maxq=a[i];
		if(ok){
			F(j,maxq+1,n) f[i][j]=(f[i][j]+1)%Mod;
			ok=oo;
		}
		vis[a[i]]=1;
	}
	printf("%d\n",f[n][n]);
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		F(i,1,n) scanf("%d",a+i);
		if(n<=1000) solve1();
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1652.02 us3 MB + 864 KBAcceptedScore: 4

Testcase #2656.53 us3 MB + 864 KBAcceptedScore: 4

Testcase #3656.73 us3 MB + 864 KBAcceptedScore: 4

Testcase #4655.14 us3 MB + 864 KBAcceptedScore: 4

Testcase #5656.12 us3 MB + 864 KBAcceptedScore: 4

Testcase #6656.49 us3 MB + 864 KBAcceptedScore: 4

Testcase #7653.15 us3 MB + 864 KBAcceptedScore: 4

Testcase #8651.75 us3 MB + 864 KBAcceptedScore: 4

Testcase #9651.79 us3 MB + 864 KBAcceptedScore: 4

Testcase #10652.65 us3 MB + 864 KBAcceptedScore: 4

Testcase #11653.07 us3 MB + 864 KBAcceptedScore: 4

Testcase #12787.77 us3 MB + 864 KBAcceptedScore: 4

Testcase #13831.87 us3 MB + 864 KBAcceptedScore: 4

Testcase #14844.95 us3 MB + 864 KBAcceptedScore: 4

Testcase #15890.25 us3 MB + 864 KBAcceptedScore: 4

Testcase #16960.04 us3 MB + 864 KBAcceptedScore: 4

Testcase #176.025 ms3 MB + 868 KBAcceptedScore: 4

Testcase #186.463 ms3 MB + 868 KBAcceptedScore: 4

Testcase #196.665 ms3 MB + 868 KBAcceptedScore: 4

Testcase #207.042 ms3 MB + 868 KBAcceptedScore: 4

Testcase #2138.782 ms1 MB + 40 KBWrong AnswerScore: 0

Testcase #2247.826 ms1 MB + 300 KBWrong AnswerScore: 0

Testcase #2357.112 ms1 MB + 732 KBWrong AnswerScore: 0

Testcase #2456.548 ms2 MB + 144 KBWrong AnswerScore: 0

Testcase #2554.75 ms2 MB + 312 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-18 02:46:49 | Loaded in 2 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠