QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785636#9799. Magical PaletteGrass_near_home#WA 49ms15892kbC++143.4kb2024-11-26 18:38:522024-11-26 18:38:56

Judging History

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

  • [2024-11-26 18:38:56]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:15892kb
  • [2024-11-26 18:38:52]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;

bool is_prime[MAXN];
int pre[MAXN];

int N,M;
int a[MAXN],b[MAXN];
int c[1001][1001];
int vis[MAXN];

int gcd(int n,int m){
    if(m == 0) return n;
    return gcd(m, n % m);
}

// int a[1005], b[1005];
int cnt[1000005];

bool check(int N, int M){

    if(N > M) swap(N, M);
    memset(cnt, 0, N*M*sizeof(int));
    for(int i = 1; i <= N; i++){
        a[i] = i;
    }
    for(int i = 1; i <= M; i++){
        b[i] = 1 + (i - 1) * N;
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            int t = a[i] * b[j] % (M * N);
            cnt[t] ++;
        }
    }
    for(int i=0;i<N*M;i++){
        if(cnt[i] == 0) return false;
    }
    return true;
}

bool solve(int n,int m){

    if(pre[n] > m || pre[m] > n){
        
    }
    else return false;

    N = n; M = m;
    if(gcd(N,M) != 1) return false;
    if(is_prime[N] && is_prime[M]) return true;
    // if(N < M) 
    // if(is_prime[N]){
    //     if(M < N) return true;
    //     if(pre[M] > N) return true;
    //     return false;
    // }
    // if(is_prime[M]){
    //     if(N < M) return true;
    //     if(pre[N] > M) return true;
    //     return false;
    // }
    return false;
}

void prepare(){
    cin >> N >> M;
    if(N == 1 && M == 1){
        cout << "Yes\n";
        cout << 0 << "\n" << 0 << "\n";
        return;
    }
    if(N == 1){
        cout << "Yes\n";
        cout << 1 << "\n";
        for(int i=0;i<M;i++){
            cout << i << " ";
        }
        cout << "\n";
        return ;
    }
    if(M == 1){
        cout << "Yes\n";
        for(int i=0;i<N;i++){
            cout << i << " ";
        }
        cout << "\n";
        cout << 1 << "\n";
        return ;
    }
    if(!(pre[N] > M || pre[M] > N)){
        cout << "No\n";
        return;
    }

    int flag = 0;
    if(N > M) swap(N,M), flag = 1;
    for(int i = 1; i <= N; i++){
        a[i] = i;
    }
    for(int i = 1; i <= M; i++){
        b[i] = 1 + (i - 1) * N;
    }
    cout << "Yes\n";
    if(!flag){
        for(int i = 1; i <= N; i++) cout << a[i] << " ";
        cout << "\n";
        for(int i = 1; i <= M; i++) cout << b[i] << " ";
        cout << "\n";
    }
    else{
        for(int i = 1; i <= M; i++) cout << b[i] << " ";
        cout << "\n";
        for(int i = 1; i <= N; i++) cout << a[i] << " ";
        cout << "\n";
    }
    // cout << "DEBUG:" << endl;
    // for(int i = 1; i <= N; i++){
    //     for(int j = 1; j <= M; j++){
    //         c[i][j] = a[i] * b[j] % (N * M);
    //         cout << c[i][j] << " ";
    //     }
    //     cout << endl;
    // }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 2; i < MAXN; i++){
        is_prime[i] = 1;
    }    
    for(int i = 2; i < MAXN; i++){
        if(!is_prime[i]) continue;
        pre[i] = i;
        for(int j = 2 * i; j < MAXN; j += i){
            if(is_prime[j]){
                is_prime[j] = 0;
                pre[j] = i;
            }
        }
    }
    int T;
    cin >> T;
    while(T--){
        prepare();
    }
    // for(int i=2;i<=50;i++){
    //     for(int j=2;j<=50;j++){
    //         if(check(i,j) != solve(i,j)){
    //             cout << i << " " << j << " " << check(i,j) << " " << solve(i,j) << "!!!\n";
    //         }
    //     }
    // }    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14588kb

input:

2
2 3
2 2

output:

Yes
1 2 
1 3 5 
No

result:

ok 2 cases (2 test cases)

Test #2:

score: 0
Accepted
time: 49ms
memory: 9372kb

input:

1
1 1000000

output:

Yes
1
0 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

result:

ok 1 cases (1 test case)

Test #3:

score: 0
Accepted
time: 49ms
memory: 9736kb

input:

1
1000000 1

output:

Yes
0 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok 1 cases (1 test case)

Test #4:

score: 0
Accepted
time: 3ms
memory: 10532kb

input:

1
2 500000

output:

No

result:

ok 1 cases (1 test case)

Test #5:

score: 0
Accepted
time: 30ms
memory: 14968kb

input:

1
2 499999

output:

Yes
1 2 
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 17...

result:

ok 1 cases (1 test case)

Test #6:

score: 0
Accepted
time: 6ms
memory: 9120kb

input:

1
500000 2

output:

No

result:

ok 1 cases (1 test case)

Test #7:

score: 0
Accepted
time: 27ms
memory: 15892kb

input:

1
499999 2

output:

Yes
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175...

result:

ok 1 cases (1 test case)

Test #8:

score: 0
Accepted
time: 6ms
memory: 9604kb

input:

1
3 333333

output:

No

result:

ok 1 cases (1 test case)

Test #9:

score: -100
Wrong Answer
time: 3ms
memory: 9736kb

input:

1
3 333332

output:

No

result:

wrong answer Wrong Verdict (test case 1)