QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#370476	#5045. King	zzuqy^#	WA	62ms	8552kb	C++11	1.6kb	2024-03-29 09:16:34	2024-03-29 09:16:35

Judging History

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

[2024-03-29 09:16:35]
评测

测评结果：WA
用时：62ms
内存：8552kb

查看

[2024-03-29 09:16:34]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long read()
{
    long long x;scanf("%lld",&x);return x;
}
ll quick(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return ans;
}
ll a[200010],n,p;
map<int,int>id;//表示
vector<int>pos[200010];
int ask()
{
    int x=1ll*rand()*rand()%n+1;
    while(x==n)
        x=1ll*rand()*rand()%n+1;
    int y=min(n,x+rand()%4+1ll);
    int q=a[y]*quick(a[x],p-2,p);//
    int qq=quick(q,p-2,p);
    int len=2;
    while(x!=1)//往前跳
    {
        ll v=id[a[x]*qq%p];
        if(v==0||pos[v][0]>=x)
            break;
        len++;
        x=*(lower_bound(pos[v].begin(),pos[v].end(),x)-1);

    }
    while(y!=n)
    {
        ll v=id[a[y]*qq%p];
        if(v==0||pos[v].back()<=y)
            break;
        len++;
        y=*upper_bound(pos[v].begin(),pos[v].end(),y);
    }
    return len;
}
void work()
{
    n=read();p=read();
    id.clear();
    int sum=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        pos[i].clear();
    }
    for(int i=1;i<=n;i++)
    {
        if(id[a[i]]==0)
        {
            id[a[i]]=++sum;
            pos[sum].push_back(i);
        }
    }
    int ans=-1;
    for(int i=1;i<=40;i++)
        ans=max(ans,ask());
    if(ans*2<n)
        ans=-1;
    cout<<ans<<'\n';
}
int main()
{
    srand(time(0));
    for(int t=read();t;t--)
        work();
}




// a[i]
// 下一个数是a[i+1]
// 随机一个五以内的

源文件, 语言: C++11

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 8484kb

input:

4
6 1000000007
1 1 2 4 8 16
6 1000000007
597337906 816043578 617563954 668607211 89163513 464203601
5 1000000007
2 4 5 6 8
5 1000000007
2 4 5 6 7

output:

5
-1
3
-1

result:

ok 4 number(s): "5 -1 3 -1"

Test #2:

score: -100

Wrong Answer

time: 62ms

memory: 8552kb

input:

1000
200 495189361
193302375 262009153 248101278 250233641 303504256 426913173 23261177 206011896 214770731 286184509 492688635 207979481 282629026 450810670 41818047 359796006 445343921 241742611 249404909 41291916 392252331 125287519 92825425 162555413 371172157 420486666 270651384 309213995 11709...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 2nd numbers differ - expected: '133', found: '-1'