QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#88215	#4900. 数列重排	zhouhuanyi	20	175ms	85720kb	C++23	1.3kb	2023-03-15 16:35:24	2023-03-15 16:35:28

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-15 16:35:28]
评测

测评结果：20
用时：175ms
内存：85720kb

查看

[2023-03-15 16:35:24]
提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 20000000
#define inf 1e9
#define mod 998244353
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int n,m,tans,st[N+1],F[N+1],pw[N+1],delta[N+1],delta2[N+1],l,r,X;
long long ans[N+1];
string s;
int main()
{
    int sr,maxn,res,rt;
    m=read(),l=read(),r=read(),X=read(),cin>>s,pw[0]=1;
    for (int i=1;i<=N;++i) pw[i]=233ll*pw[i-1]%mod;
    for (int i=0;i<=m-1;++i)
    {
	st[i]=X+s[i]-'0';
	if (i) st[i]+=st[i-1];
    }
    n=st[m-1];
    for (int i=l;i<=r;++i)
    {
	if (!i) ans[i]=((1ll*n*(n+1))>>1)%mod;
	else
	{
	    sr=n-st[i-1];
	    for (int j=1;j<=st[i-1]+1;++j) F[j]=1;
	    for (int j=i+1;j<=st[i-1]+1;++j) ans[i]+=j-i;
	    for (int j=1;j<=sr;++j)
	    {
		for (int k=1;k<=st[i-1]+1;++k) delta[k]=delta[k-1]+F[k];
		delta2[st[i-1]+1]=rt=maxn=0;
		for (int k=st[i-1]+1;k>=1;--k) delta2[k]=delta2[k+1]+F[k];
		for (int k=1;k<=st[i-1]+1;++k)
		{
		    res=0;
		    if (k-i>=1) res+=delta[k-i];
		    if (k+i<=st[i-1]+1) res+=delta2[k+i];
		    if (res>maxn) maxn=res,rt=k;
		}
		ans[i]+=maxn,F[rt]++;
	    }
	}
    }
    for (int i=l;i<=r;++i) tans^=(1ll*(ans[i]%mod)*pw[i]%mod);
    printf("%d\n",tans);
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 89ms

memory: 85456kb

input:

2 0 2 2
01

output:

result:

ok 1 number(s): "541257"

Test #2:

score: 0

Accepted

time: 99ms

memory: 83884kb

input:

4 1 4 2
00001

output:

525797597

result:

ok 1 number(s): "525797597"

Test #3:

score: 0

Accepted

time: 101ms

memory: 85428kb

input:

9 0 9 1
000000000

output:

711136343

result:

ok 1 number(s): "711136343"

Test #4:

score: 0

Accepted

time: 94ms

memory: 85632kb

input:

1 0 1 9
0

output:

result:

ok 1 number(s): "10456"

Test #5:

score: 0

Accepted

time: 94ms

memory: 83840kb

input:

2 1 2 3
11

output:

result:

ok 1 number(s): "1518844"

Subtask #2:

score: 15

Accepted

Dependency #1:

100%

Accepted

Test #6:

score: 15

Accepted

time: 120ms

memory: 84340kb

input:

21 0 21 9
111010011100100100000

output:

171658329

result:

ok 1 number(s): "171658329"

Test #7:

score: 0

Accepted

time: 91ms

memory: 83792kb

input:

200 0 200 1
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

output:

287932632

result:

ok 1 number(s): "287932632"

Test #8:

score: 0

Accepted

time: 102ms

memory: 85000kb

input:

120 3 119 1
101000110101001100011100001011101110101010000011101110010101101000111100111100001001010010110001110011001010110001101111

output:

856785458

result:

ok 1 number(s): "856785458"

Test #9:

score: 0

Accepted

time: 104ms

memory: 85720kb

input:

2 0 2 99
10

output:

67513337

result:

ok 1 number(s): "67513337"

Subtask #3:

score: 0

Time Limit Exceeded

Dependency #2:

100%

Accepted

Test #10:

score: 15

Accepted

time: 175ms

memory: 83936kb

input:

10 1 9 499
0110011010

output:

47418354

result:

ok 1 number(s): "47418354"

Test #11:

score: -15

Time Limit Exceeded

input:

100 0 100 49
1100100011111101111111001000000100010000101010110000011011110100100011111000111101100010001000001100

output:

result:

Subtask #4:

score: 0

Time Limit Exceeded

Test #14:

score: 0

Time Limit Exceeded

input:

2 0 1 114514
10

output:

result:

Subtask #5:

score: 0

Runtime Error

Test #17:

score: 0

Runtime Error

input:

1000000 1000000 1000000 928
01100010010000000101111110001111011101111000011110100101011110011001001000011000110101101100111110000100101010111001111100010011100110000000111110110100001100000000011101100001010001010000010000001001000110011111010101111100001001110110010100000011000010010001111010011100...

output:

result:

Subtask #6:

score: 0

Time Limit Exceeded

Test #19:

score: 0

Time Limit Exceeded

input:

1000000 0 1000000 1
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

result:

Subtask #7:

score: 0

Time Limit Exceeded

Test #21:

score: 0

Time Limit Exceeded

input:

1000000 0 9823 627
01110001011101001100010011100101001011000011011110001101010000000101010111110111110010010001110100101001111000111100011101111001000000100111000010010100010101110110111110100010101010001110111001100011010001111000101010000110010010101110101010111110110001110111111000001110000110011...

output:

result:

Subtask #8:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

Subtask #9:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted