結果

問題 No.1711 Divide LCM
ユーザー 👑 ygussany
提出日時 2021-10-15 23:25:11
言語 C
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 3,834 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 34,944 KB
実行使用メモリ 21,356 KB
最終ジャッジ日時 2024-09-17 18:31:25
合計ジャッジ時間 193,049 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 RE * 1
other AC * 10 WA * 22 RE * 5 TLE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'shuffle_permutation':
main.c:58:28: warning: 'return' with a value, in function returning void
   58 |         if (N == 1) return 0;
      |                            ^
main.c:56:6: note: declared here
   56 | void shuffle_permutation(int N, int p[], int K)
      |      ^~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define MT_N 624
#define MT_M 397
#define MT_MATRIX_A 0x9908b0dfUL
#define MT_UPPER_MASK 0x80000000UL
#define MT_LOWER_MASK 0x7fffffffUL
static unsigned int mt[MT_N];
static int mti = MT_N + 1;
void init_genrand(unsigned int s)
{
    mt[0] = s & 0xffffffffUL;
    for (mti = 1; mti < MT_N; mti++) {
        mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
        mt[mti] &= 0xffffffffUL;
    }
}
unsigned int genrand()
{
    unsigned int y;
    static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A};
    if (mti >= MT_N) {
        int kk;
        if (mti == MT_N + 1) init_genrand(5489UL);
        
        for (kk = 0; kk < MT_N - MT_M; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        for (; kk < MT_N - 1; kk++) {
            y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK);
            mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL];
        }
        y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK);
        mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL];
        mti = 0;
    }
  
    y = mt[mti++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680UL;
    y ^= (y << 15) & 0xefc60000UL;
    y ^= (y >> 18);
    return y;
}
void shuffle_permutation(int N, int p[], int K)
{
    if (N == 1) return 0;
    
    int i, j, k;
    for (k = 0; k < K; k++) {
        do {
            i = genrand() % N + 1;
            j = genrand() % N + 1;
        } while (i == j);
        p[i] ^= p[j];
        p[j] ^= p[i];
        p[i] ^= p[j];
    }
}
void chmax(int* a, int b)
{
    if (*a < b) *a = b;
}
typedef struct Edge {
    struct Edge *next;
    int v;
} edge;
int main()
{
    init_genrand(46);
    struct timeval t;
    double beg, cur;
    gettimeofday(&t, NULL);
    beg = t.tv_sec + (double)t.tv_usec / 1000000;
    
    int i, j, k = 0, l, N, A[100001], prime[100001], max[100001], flag[1000001] = {}, m[100001], *p[100001], *e[100001];
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
        scanf("%d", &(m[i]));
        p[i] = (int*)malloc(sizeof(int) * (m[i] + 1));
        e[i] = (int*)malloc(sizeof(int) * (m[i] + 1));
        for (j = 1, A[i] = 1; j <= m[i]; j++) {
            scanf("%d %d", &(p[i][j]), &(e[i][j]));
            for (l = 0; l < e[i][j]; l++) A[i] *= p[i][j];
            if (flag[p[i][j]] == 0) {
                prime[++k] = p[i][j];
                max[k] = e[i][j];
                flag[p[i][j]] = k;
            } else chmax(&(max[flag[p[i][j]]]), e[i][j]);
        }
    }
    
    edge *adj[100001] = {}, ed[1000001], *po;
    for (i = 1, l = 0; i <= N; i++) {
        for (j = 1; j <= m[i]; j++) {
            if (e[i][j] != max[flag[p[i][j]]]) continue;
            ed[l].v = i;
            ed[l].next = adj[flag[p[i][j]]];
            adj[flag[p[i][j]]] = &(ed[l++]);
        }
    }
    
    int q[100001], live[100001], ans = k + 1, q_ans[100001];
    for (i = 1; i <= k; i++) q[i] = i;
    shuffle_permutation(k, q, k * 10);
    while (1) {
        gettimeofday(&t, NULL);
        cur = t.tv_sec + (double)t.tv_usec / 1000000;
        if (cur - beg > 3.99) break;
        
        for (i = 1; i <= N; i++) live[i] = 1;
        for (i = 1; i <= k; i++) {
            j = q[i];
            for (po = adj[j], live[0] = 0; po != NULL; po = po->next) {
                if (live[po->v] == i) {
                    live[po->v]++;
                    live[0] = 1;
                }
            }
            if (live[0] == 0) break;
        }
        if (ans > i) {
            ans = i;
            for (i = 1; i <= k; i++) q_ans[i] = q[i];
        }
        
        shuffle_permutation(k, q, 1000 + genrand() % 2);
    }
    
    if (ans == k + 1) {
        printf("-1\n");
        fflush(stdout);
        return -1;
    }
    
    int num[100001] = {};
    printf("%d\n", ans);
    for (i = 1; i <= N; i++) live[i] = 1;
    for (i = 1; i <= ans; i++) {
        j = q[i];
        for (po = adj[j]; po != NULL; po = po->next) if (live[po->v] == i) live[po->v]++;
    }
    for (i = 1; i <= N; i++) num[live[i]]++;
    for (i = 1; i <= ans; i++) {
        printf("%d", num[i]);
        for (j = 1; j <= N; j++) if (live[j] == i) printf(" %d", A[j]);
        printf("\n");
    }
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0