/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 4ms 3.02 MiB
#2 Wrong Answer 35ms 39.227 MiB

Code

#include <stdio.h>

void sieve(int spf[], int n) {
    for (int i = 0; i <= n; i++) spf[i] = i; 
    for (int i = 2; i * i <= n; i++) {
        if (spf[i] == i) {  // i is prime
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j) spf[j] = i; 
            }
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    
    int spf[100001];
    sieve(spf, 100000);
    
    while (t--) {
        int n;
        scanf("%d", &n);
        int C[n], A[n];
        
        for (int i = 0; i < n; i++) {
            scanf("%d", &C[i]);
        }
        
        int groups[100001][n], sizes[100001] = {0};
        
       
        for (int i = 0; i < n; i++) {
            int prime = spf[i + 1];
            groups[prime][sizes[prime]++] = i;
        }

        int possible = 1;

        for (int prime = 1; prime <= 100000; prime++) {
            if (sizes[prime] == 0) continue; 

            int group_size = sizes[prime];
            int indices[group_size], C_values[group_size];
            
            for (int i = 0; i < group_size; i++) {
                indices[i] = groups[prime][i];
                C_values[i] = C[indices[i]];
            }

            for (int i = 0; i < group_size - 1; i++) {
                for (int j = i + 1; j < group_size; j++) {
                    if (C_values[i] > C_values[j]) {
                        int temp = C_values[i]; C_values[i] = C_values[j]; C_values[j] = temp;
                        temp = indices[i]; indices[i] = indices[j]; indices[j] = temp;
                    }
                }
            }

            for (int i = 0; i < group_size; i++) {
                if (C_values[i] < i) {
                    possible = 0;
                    break;
                }
                A[indices[i]] = 1000000000 - i;
            }

            if (!possible) break;
        }

        if (possible) {
            printf("YES\n");
            for (int i = 0; i < n; i++) {
                printf("%d ", A[i]);
            }
            printf("\n");
        } else {
            printf("NO\n");
        }
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1163 Roy and Array Construction
Contest
Brain Booster #8
Language
C99 (GCC 13.2.0)
Submit At
2025-02-17 16:38:43
Judged At
2025-02-17 16:38:43
Judged By
Score
0
Total Time
35ms
Peak Memory
39.227 MiB