結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0