QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#529371	#6399. Classic: Classical Problem	solar_express^#	TL	4163ms	6148kb	C++20	2.5kb	2024-08-24 12:42:27	2024-08-24 12:42:27

Judging History

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

[2024-08-24 12:42:27]
评测

测评结果：TL
用时：4163ms
内存：6148kb

查看

[2024-08-24 12:42:27]
提交

answer

#include<bits/stdc++.h>
#define N 200005
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<400000> 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);
            // cerr<<(p-1)-id[a[i]]+1<<" "<<2*(p-1)-id[a[i]]+1<<endl;
        }
        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]+1);
            // cerr<<(p-1)-id[i]+1<<" "<<2*(p-1)-id[i]+1<<endl;
            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%(p-1)+1]);
                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%(p-1)+1]);
            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: 3820kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok 6 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 5796kb

input:

output:

result:

ok 14 lines

Test #4:

score: 0

Accepted

time: 2ms

memory: 5848kb

input:

output:

result:

ok 62 lines

Test #5:

score: 0

Accepted

time: 5ms

memory: 3812kb

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: 147ms

memory: 5916kb

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: 632ms

memory: 5920kb

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: 775ms

memory: 4112kb

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: 664ms

memory: 3876kb

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: 0

Accepted

time: 543ms

memory: 5896kb

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:

ok 20000 lines

Test #11:

score: 0

Accepted

time: 4163ms

memory: 6116kb

input:

10000
10 11
6 8 0 1 7 3 2 9 4 5
21 23
21 19 10 17 11 20 6 3 2 18 9 16 13 14 4 12 8 7 1 0 15
7 7
6 2 4 0 1 5 3
17 19
4 6 5 11 17 15 0 10 3 8 12 18 13 7 9 2 14
15 17
11 15 8 2 12 3 1 13 16 6 7 0 9 10 5
2 2
0 1
2 2
0 1
33 37
11 20 9 16 19 32 33 31 3 29 36 10 8 25 22 17 5 6 15 28 14 0 4 27 18 12 34 21 3...

output:

1 10
1 
1 19
4 
6 7
1 2 3 4 5 6 
1 14
14 
1 14
12 
1 2
1 
1 2
1 
2 21
21 24 
1 8
8 
6 7
1 2 3 4 5 6 
10 11
1 2 3 4 5 6 7 8 9 10 
1 22
22 
1 6
1 
1 10
11 
1 26
22 
2 3
1 2 
1 14
16 
22 23
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
2 4
2 6 
1 18
3 
6 7
1 2 3 4 5 6 
1 2
1 
1 8
7 
1 28
15...

result:

ok 20000 lines

Test #12:

score: 0

Accepted

time: 962ms

memory: 6148kb

input:

10000
4 13
4 5 0 6
12 31
0 16 11 13 3 24 26 21 20 6 5 19
12 43
29 21 40 23 31 24 27 17 30 10 0 42
3 3
0 2 1
15 47
41 46 0 44 17 39 30 4 12 14 36 28 27 31 10
1 5
0
5 11
6 2 0 5 1
6 13
11 0 7 5 10 6
5 17
15 0 9 12 11
6 13
0 5 2 12 11 7
15 43
14 28 13 24 40 29 37 9 27 0 34 39 15 12 2
1 3
0
8 17
15 6 0 ...

output:

3 2
8 10 11 
1 6
6 
2 3
33 41 
2 3
1 2 
3 3
31 37 41 
5 1
0 1 2 3 4
2 3
1 2 
2 3
4 8 
4 2
2 8 10 14 
1 3
12 
1 4
14 
3 1
0 1 2
1 4
8 
2 1
0 1
3 2
4 9 10 
4 2
1 3 5 12 
1 2
3 
5 2
3 12 15 16 18 
7 1
0 1 2 3 4 5 6
5 2
2 5 15 16 18 
10 2
2 6 8 11 19 25 27 29 34 35 
3 2
2 7 9 
1 2
2 
3 3
7 14 15 
2 5
36...

result:

ok 20000 lines

Test #13:

score: 0

Accepted

time: 1471ms

memory: 5920kb

input:

10000
13 19
13 6 0 9 15 2 4 10 3 5 11 12 14
5 11
5 8 10 0 6
2 3
0 1
1 2
0
10 19
6 16 2 1 17 0 4 10 5 7
4 7
0 1 4 2
41 73
55 47 13 35 18 68 3 25 67 36 70 69 62 37 56 64 49 72 12 0 4 17 31 8 66 63 2 16 65 60 24 26 7 21 33 52 54 39 29 53 71
1 3
0
26 61
43 0 37 54 47 49 17 38 19 28 35 18 39 36 33 34 8 2...

output:

1 6
13 
2 3
7 9 
1 2
1 
2 1
0 1
1 4
10 
3 3
1 2 4 
1 12
72 
3 1
0 1 2
2 5
10 17 
1 7
11 
1 7
27 
1 4
8 
2 3
1 2 
2 3
1 2 
1 2
1 
1 2
2 
1 6
6 
1 8
31 
1 4
13 
1 3
3 
1 4
12 
3 5
1 2 7 
1 7
5 
1 2
4 
3 1
0 1 2
2 1
0 1
2 4
4 6 
1 2
4 
2 2
1 10 
2 4
10 12 
2 4
4 6 
1 2
2 
2 6
3 5 
7 1
0 1 2 3 4 5 6
2 4...

result:

ok 20000 lines

Test #14:

score: 0

Accepted

time: 2274ms

memory: 5920kb

input:

10000
2 3
0 2
38 61
50 55 35 52 17 40 15 51 39 11 5 41 2 33 49 25 0 24 53 13 30 59 9 34 57 37 38 27 29 1 19 31 46 8 45 58 6 42
11 17
5 13 1 11 2 0 6 7 4 12 10
6 11
3 0 4 7 10 6
21 29
17 14 7 18 20 28 23 25 16 3 22 5 21 2 0 9 13 1 12 11 19
5 5
0 3 2 1 4
20 23
19 16 0 1 15 18 14 12 21 6 22 8 11 13 20 ...

output:

result:

ok 20000 lines

Test #15:

score: -100

Time Limit Exceeded

input:

10000
17 17
1 5 10 2 16 6 12 13 15 3 8 9 11 4 14 7 0
67 67
34 11 54 25 8 40 33 24 2 44 22 5 28 46 23 59 30 1 38 18 55 15 35 6 39 64 27 51 65 12 52 53 58 20 14 19 29 43 0 9 62 45 41 42 47 49 31 32 26 57 37 48 7 36 17 13 10 50 63 3 16 21 4 61 66 56 60
3 3
1 0 2
3 3
2 0 1
5 5
4 0 2 1 3
13 13
8 1 5 10 4...

output:

16 17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
66 67
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 
2 3
1 2 
2 3
1 2 
4 5
1 2 3 4 
12 13
1 2 3 4 5 6 7 8 9 10 ...