QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#529357	#6399. Classic: Classical Problem	solar_express^#	WA	503ms	4040kb	C++20	2.3kb	2024-08-24 12:29:04	2024-08-24 12:29:04

Judging History

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

[2024-08-24 12:29:04]
评测

测评结果：WA
用时：503ms
内存：4040kb

查看

[2024-08-24 12:29:04]
提交

answer

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int T,n,p,a[N];
int id[N],invid[N];
int vis[N];
int gen(){
    for(int i=2;i<p;++i){
        for(int j=0;j<p;++j) vis[j]=0;
        int val=1;
        bool fl=0;
        for(int j=1;j<p;++j){
            if(vis[val]){
                fl=1;
                break;
            }
            vis[val]=1;
            val=1ll*val*i%p;
        }
        if(fl==0) return i;
    }
}
bitset<200000> b,ans,c;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>p;
        int g=gen();
        // cerr<<"g:"<<p<<" "<<g<<endl;
        int val=1;
        for(int i=1;i<=p-1;++i){
            id[val]=i;
            invid[i]=val;
            val=1ll*val*g%p;
        }
        bool fl=0,fl2=0;
        for(int i=1;i<=n;++i){
            cin>>a[i];
            if(a[i]==0) fl=1;
            else fl2=1;
        }
        if(fl==0){
            cout<<"1 1\n";
            cout<<"0\n";
            continue;
        }
        if(fl2==0){
            cout<<p<<" 1\n";
            for(int i=0;i<p;++i)
                cout<<i<<" \n"[i==p-1];
            continue;
        }
        b.reset();
        for(int i=1;i<=n;++i) if(a[i]!=0) b.set((p-1)-id[a[i]]+1),b.set(2*(p-1)-id[a[i]]+1);
        for(int i=1;i<p;++i) ans.set(i);
        fl=0;
        for(int i=1;i<p;++i){
            c=(b>>((p-1)-id[i]))|(b>>(2*(p-1)-id[i]));
            if((c&ans).count()){
                ans=c&ans;
            }else{
                // cout<<"ans ";
                cout<<ans.count()<<" "<<i<<'\n';
                vector<int> a;
                a.clear();
                for(int j=1;j<p;++j)
                    if(ans[j])
                        a.push_back(invid[j]);
                sort(a.begin(),a.end());
                for(auto val:a) cout<<val<<" ";
                cout<<'\n';
                fl=1;
                break;
            }
        }
        if(fl==0){
            cout<<ans.count()<<" "<<p<<'\n';
            vector<int> a;
            a.clear();
            for(int j=1;j<p;++j)
                if(ans[j])
                    a.push_back(invid[j]);
            sort(a.begin(),a.end());
            for(auto val:a) cout<<val<<" ";
            cout<<'\n';
        }
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3720kb

input:

output:

result:

ok 6 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok 14 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3788kb

input:

output:

result:

ok 62 lines

Test #5:

score: 0

Accepted

time: 6ms

memory: 3784kb

input:

output:

7 1
0 1 2 3 4 5 6
1 1
0
1 2
1 
1 1
0
1 2
4 
1 1
0
1 3
1 
1 1
0
1 2
5 
1 1
0
2 2
1 5 
1 1
0
2 2
4 5 
1 1
0
1 4
1 
1 1
0
1 2
2 
1 1
0
1 3
2 
1 1
0
1 3
4 
1 1
0
3 3
1 2 4 
1 1
0
2 2
2 5 
1 1
0
1 3
2 
1 1
0
1 3
4 
1 1
0
1 5
1 
1 1
0
1 2
3 
1 1
0
2 2
1 3 
1 1
0
2 2
3 4 
1 1
0
1 3
1 
1 1
0
1 3
3 
1 1
0
1 ...

result:

ok 254 lines

Test #6:

score: 0

Accepted

time: 96ms

memory: 3732kb

input:

output:

11 1
0 1 2 3 4 5 6 7 8 9 10
1 1
0
1 2
1 
1 1
0
1 2
6 
1 1
0
1 3
1 
1 1
0
1 2
4 
1 1
0
2 2
1 4 
1 1
0
2 2
4 6 
1 1
0
1 4
1 
1 1
0
1 2
3 
1 1
0
2 2
1 3 
1 1
0
1 3
6 
1 1
0
2 3
1 6 
1 1
0
2 2
3 4 
1 1
0
3 2
1 3 4 
1 1
0
1 3
6 
1 1
0
1 5
1 
1 1
0
1 2
9 
1 1
0
2 2
1 9 
1 1
0
2 2
6 9 
1 1
0
1 3
1 
1 1
0
2...

result:

ok 4094 lines

Test #7:

score: 0

Accepted

time: 408ms

memory: 4028kb

input:

output:

13 1
0 1 2 3 4 5 6 7 8 9 10 11 12
1 1
0
1 2
1 
1 1
0
1 2
7 
1 1
0
1 3
1 
1 1
0
1 2
9 
1 1
0
2 2
1 9 
1 1
0
2 2
7 9 
1 1
0
1 4
1 
1 1
0
1 2
10 
1 1
0
2 2
1 10 
1 1
0
1 3
7 
1 1
0
2 3
1 7 
1 1
0
2 2
9 10 
1 1
0
3 2
1 9 10 
1 1
0
1 3
7 
1 1
0
1 5
1 
1 1
0
1 2
8 
1 1
0
2 2
1 8 
1 1
0
2 2
7 8 
1 1
0
1 3
...

result:

ok 16382 lines

Test #8:

score: 0

Accepted

time: 503ms

memory: 4040kb

input:

output:

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

result:

ok 23528 lines

Test #9:

score: 0

Accepted

time: 431ms

memory: 3724kb

input:

output:

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

result:

ok 21052 lines

Test #10:

score: -100

Wrong Answer

time: 348ms

memory: 3732kb

input:

10000
9 83
60 35 63 59 58 81 0 13 71
1 5
0
1 7
0
2 61
39 0
2 7
0 4
1 7
0
2 19
0 14
1 2
0
3 23
14 10 0
3 11
0 5 2
1 5
0
2 7
0 4
2 3
0 2
2 3
0 1
1 13
0
5 47
10 2 34 15 0
1 2
0
1 17
0
1 11
0
2 7
1 0
1 7
0
2 23
0 17
2 13
10 0
2 7
1 0
6 31
19 13 6 29 0 24
4 23
0 5 18 17
2 19
0 5
1 7
0
2 13
7 0
3 17
0 6 1...

output:

2 3
38 76 
5 1
0 1 2 3 4
7 1
0 1 2 3 4 5 6
1 2
36 
1 2
2 
7 1
0 1 2 3 4 5 6
1 2
15 
2 1
0 1
2 2
5 7 
2 2
6 9 
5 1
0 1 2 3 4
1 2
2 
1 2
2 
1 2
1 
13 1
0 1 2 3 4 5 6 7 8 9 10 11 12
4 2
18 22 24 33 
2 1
0 1
17 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
11 1
0 1 2 3 4 5 6 7 8 9 10
1 2
1 
7 1
0 1 2 3 4 5...

result:

wrong answer 317th lines differ - expected: '1 2', found: '2 2'