結果

問題 No.1711 Divide LCM
ユーザー ygussanyygussany
提出日時 2021-10-15 23:40:17
言語 C
(gcc 12.3.0)
結果
RE  
実行時間 -
コード長 3,868 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 34,944 KB
実行使用メモリ 20,848 KB
最終ジャッジ日時 2024-09-17 18:45:16
合計ジャッジ時間 61,134 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 AC 3,985 ms
15,732 KB
testcase_19 AC 3,987 ms
13,952 KB
testcase_20 AC 3,986 ms
15,896 KB
testcase_21 AC 3,990 ms
19,184 KB
testcase_22 AC 3,984 ms
16,744 KB
testcase_23 AC 3,983 ms
15,200 KB
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 AC 3,987 ms
18,020 KB
testcase_28 WA -
testcase_29 RE -
testcase_30 AC 3,988 ms
16,300 KB
testcase_31 RE -
testcase_32 AC 3,990 ms
19,192 KB
testcase_33 WA -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 AC 3,990 ms
18,964 KB
testcase_39 AC 3,990 ms
20,848 KB
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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()
{
	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]);
		}
	}
	if (k < 50) return -1;
	
	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