提交记录 3819


用户 题目 状态 得分 用时 内存 语言 代码长度
PinkRabbit noi18b. 【NOI2018】冒泡排序 Wrong Answer 80 57.099 ms 3940 KB C++ 909 B
提交时间 评测时间
2018-07-18 18:26:52 2020-07-31 21:46:05
#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 #1651.89 us3 MB + 864 KBAcceptedScore: 4

Testcase #2655.97 us3 MB + 864 KBAcceptedScore: 4

Testcase #3656.62 us3 MB + 864 KBAcceptedScore: 4

Testcase #4655.82 us3 MB + 864 KBAcceptedScore: 4

Testcase #5655.45 us3 MB + 864 KBAcceptedScore: 4

Testcase #6657.37 us3 MB + 864 KBAcceptedScore: 4

Testcase #7652.84 us3 MB + 864 KBAcceptedScore: 4

Testcase #8652.65 us3 MB + 864 KBAcceptedScore: 4

Testcase #9653.58 us3 MB + 864 KBAcceptedScore: 4

Testcase #10652.24 us3 MB + 864 KBAcceptedScore: 4

Testcase #11653.73 us3 MB + 864 KBAcceptedScore: 4

Testcase #12787.59 us3 MB + 864 KBAcceptedScore: 4

Testcase #13830.65 us3 MB + 864 KBAcceptedScore: 4

Testcase #14845.06 us3 MB + 864 KBAcceptedScore: 4

Testcase #15890.24 us3 MB + 864 KBAcceptedScore: 4

Testcase #16962.61 us3 MB + 864 KBAcceptedScore: 4

Testcase #175.948 ms3 MB + 868 KBAcceptedScore: 4

Testcase #186.468 ms3 MB + 868 KBAcceptedScore: 4

Testcase #196.664 ms3 MB + 868 KBAcceptedScore: 4

Testcase #207.042 ms3 MB + 868 KBAcceptedScore: 4

Testcase #2138.809 ms1 MB + 40 KBWrong AnswerScore: 0

Testcase #2247.786 ms1 MB + 300 KBWrong AnswerScore: 0

Testcase #2357.099 ms1 MB + 732 KBWrong AnswerScore: 0

Testcase #2456.571 ms2 MB + 144 KBWrong AnswerScore: 0

Testcase #2554.737 ms2 MB + 312 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2026-04-17 23:36:28 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠