QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#867197#8820. Exchanging Kubic 2lsj2009WA 56ms3840kbC++143.3kb2025-01-23 10:46:002025-01-23 10:46:11

Judging History

This is the latest submission verdict.

  • [2025-01-23 10:46:11]
  • Judged
  • Verdict: WA
  • Time: 56ms
  • Memory: 3840kb
  • [2025-01-23 10:46:00]
  • Submitted

answer

#include<bits/stdc++.h>
// #define int long long
#pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
template<int p>
struct mint {
	int x;
	mint() {
		x=0;
	}
	mint(int _x) {
		if(_x<0)
			_x+=p;
		x=_x;
	}
	friend mint operator + (mint a,mint b) {
		return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
	}
	friend mint operator - (mint a,mint b)  {
		return a.x<b.x? a.x-b.x+p:a.x-b.x;
	}
	friend mint operator * (mint a,mint b) {
		return 1ll*a.x*b.x%p;
	}
	friend mint operator ^ (mint a,ll b) {
		mint res=1,base=a;
		while(b) {
			if(b&1)
				res*=base;
			base*=base; b>>=1;
		}
		return res;
	}
	friend mint operator ~ (mint a) {
		return a^(p-2);
	}
	friend mint operator / (mint a,mint b) {
		return a*(~b);
	}
	friend mint & operator += (mint& a,mint b) {
		return a=a+b;
	}
	friend mint & operator -= (mint& a,mint b) {
		return a=a-b;
	}
	friend mint & operator *= (mint& a,mint b) {
		return a=a*b;
	}
	friend mint & operator /= (mint& a,mint b) {
		return a=a/b;
	}
	friend mint operator ++ (mint& a) {
		return a+=1;
	}
	friend mint operator -- (mint& a) {
		return a-=1;
	}
};
const int MOD=998244353;
#define mint mint<MOD>
const int N=4e2+5,M=8e2+5;
mint f[2][4][M];
bool used[N][M];
void solve() {
    int n;
    scanf("%d",&n);
    rep(i,1,n) {
		int m;
		scanf("%d",&m);
        while(m--) {
			int x;
			scanf("%d",&x);
			used[i][x]=true;
		}
    }
	mint res=0;
    rep(v,-n,800) {
		int p=0;
		rep(k,0,3) {
			rep(j,0,800)
				f[p][k][j]=0;
		}
		f[p][0][0]=1;
		rep(i,1,n) {
			p^=1;
			rep(k,0,3) {
				rep(j,0,800)
					f[p][k][j]=0;
			}
			rep(k,0,3) {
				mint tot=0;
				rep(j,0,800) {
					tot+=f[p^1][k][j];
					if(j-i>=v&&used[i][j])
						f[p][k|((j-i==v)<<1)|(j-i>=v+n)][j]+=tot;
				}
			}
		}
		rep(i,0,800)
			res+=mint(-v-n+1)*f[p][3][i];
    }
    rep(v,-n,800) {
		int p=0;
		rep(i,0,n) {
			rep(k,0,1) {
				rep(j,0,800)
					f[p][k][j]=0;
			}
		}
		f[p][0][0]=1;
		rep(i,1,n) {
			p^=1;
			rep(k,0,3) {
				rep(j,0,800)
					f[p][k][j]=0;
			}
			rep(k,0,3) {
				mint tot=0;
				rep(j,0,800) {
					tot+=f[p^1][k][j];
					if(j-i<=v&&used[i][j])
						f[p][k|((j-i==v)<<1)|(j-i<=v-n)][j]+=tot;
				}
			}
		}
		rep(i,0,800)
			res+=mint(v)*f[p][3][i];
    }
	printf("%d\n",res.x);
}
bool M2;
// g++ QOJ8820.cpp -std=c++14 -Wall -O2 -o QOJ8820
signed main() {
    // file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 29ms
memory: 3840kb

input:

5
3 1 2 3
1 2
0
4 0 2 3 4
2 2 3

output:

0

result:

ok "0"

Test #2:

score: 0
Accepted
time: 29ms
memory: 3840kb

input:

5
4 1 2 3 7
4 5 7 8 9
4 2 3 6 9
5 0 1 4 7 9
8 0 1 2 3 6 7 8 9

output:

16

result:

ok "16"

Test #3:

score: 0
Accepted
time: 56ms
memory: 3840kb

input:

10
8 1 2 3 7 15 17 18 19
11 1 2 5 8 9 10 13 16 18 19 20
12 0 1 4 5 6 7 8 9 11 16 17 19
12 0 1 3 5 9 10 11 15 16 17 18 19
6 2 8 11 15 18 19
11 0 4 6 7 8 10 11 13 16 18 19
13 1 3 4 6 8 9 10 12 13 14 15 19 20
13 2 4 5 8 9 10 11 13 14 15 16 17 20
10 2 3 5 6 8 10 13 14 18 19
12 2 3 4 5 8 9 12 13 15 16 19...

output:

27895

result:

ok "27895"

Test #4:

score: -100
Wrong Answer
time: 55ms
memory: 3840kb

input:

10
12 0 3 4 5 6 7 8 13 14 17 19 20
15 0 1 2 4 5 6 8 9 11 12 13 14 15 18 19
9 2 7 8 9 13 15 16 18 19
17 0 1 2 3 4 5 6 7 8 9 10 11 15 16 17 18 19
17 0 1 2 4 6 7 8 9 10 11 12 14 15 16 17 19 20
17 0 1 2 3 6 8 10 11 12 13 14 15 16 17 18 19 20
15 1 3 4 6 7 9 10 11 12 13 14 15 17 19 20
16 0 1 2 3 5 6 8 9 1...

output:

4148600

result:

wrong answer 1st words differ - expected: '625955', found: '4148600'