結果

問題 No.1711 Divide LCM
ユーザー 👑 ygussany
提出日時 2021-10-15 23:28:55
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,863 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 35,328 KB
実行使用メモリ 20,968 KB
最終ジャッジ日時 2024-09-17 18:36:02
合計ジャッジ時間 190,982 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.98) 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 0;
	}
	
	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]);
		if (num[i] == 0) return -1;
		for (j = 1; j <= N; j++) if (live[j] == i) printf(" %d", A[j]);
		printf("\n");
	}
	fflush(stdout);
	return 0;
}
0