QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83685 | #2347. Traffic Blights | little_sun | AC ✓ | 470ms | 5768kb | C++14 | 1.8kb | 2023-03-03 02:34:08 | 2023-03-03 02:34:08 |
Judging History
answer
#include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)
const int M = 2520;
const int MaxN = 5e2 + 5;
const double eps = 1e-10;
double ans[MaxN], tmp[MaxN], sum[MaxN];
int n, m[MaxN], d[MaxN][MaxN], vis[MaxN][MaxN];
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
int get(int x) {
if (x == 2 || x == 4)
return 8;
else if (x == 3)
return 9;
else
return x;
}
inline int read() {
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
void calc(int r) {
memset(vis, 0, sizeof(vis)), tmp[0] = 1;
for (int i = 1; i <= n; i++)
tmp[i] = 0;
for (int i = 1; i <= 100; i++)
sum[i] = 1;
for (int i = 1; i <= n; i++) {
int v = get(m[i] / gcd(m[i], M));
if (tmp[i - 1] < eps)
break;
double last = sum[v];
for (int k = 0; k < v; k++) {
int cur = r + k * M;
if (d[i][cur % m[i]] && !vis[v][k])
sum[v] -= 1.0 / v, vis[v][k] = 1;
}
tmp[i] = tmp[i - 1] * sum[v] / last;
}
for (int i = 0; i <= n; i++)
ans[i] += tmp[i];
}
signed main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x = read(), r = read(), g = read();
m[i] = r + g;
for (int j = 0; j < r; j++)
d[i][(j - x % m[i] + m[i]) % m[i]] = 1;
}
for (int i = 0; i < M; i++)
calc(i);
for (int i = 0; i <= n; i++)
printf("%.15lf\n", (ans[i] - ans[i + 1]) / M);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 95ms
memory: 4784kb
Test #2:
score: 0
Accepted
time: 98ms
memory: 4584kb
Test #3:
score: 0
Accepted
time: 86ms
memory: 4624kb
Test #4:
score: 0
Accepted
time: 89ms
memory: 4772kb
Test #5:
score: 0
Accepted
time: 92ms
memory: 4776kb
Test #6:
score: 0
Accepted
time: 99ms
memory: 4608kb
Test #7:
score: 0
Accepted
time: 94ms
memory: 4600kb
Test #8:
score: 0
Accepted
time: 88ms
memory: 4632kb
Test #9:
score: 0
Accepted
time: 90ms
memory: 4596kb
Test #10:
score: 0
Accepted
time: 97ms
memory: 4632kb
Test #11:
score: 0
Accepted
time: 93ms
memory: 4696kb
Test #12:
score: 0
Accepted
time: 91ms
memory: 4568kb
Test #13:
score: 0
Accepted
time: 92ms
memory: 4816kb
Test #14:
score: 0
Accepted
time: 91ms
memory: 4788kb
Test #15:
score: 0
Accepted
time: 95ms
memory: 4788kb
Test #16:
score: 0
Accepted
time: 94ms
memory: 4680kb
Test #17:
score: 0
Accepted
time: 94ms
memory: 4664kb
Test #18:
score: 0
Accepted
time: 93ms
memory: 4700kb
Test #19:
score: 0
Accepted
time: 85ms
memory: 4688kb
Test #20:
score: 0
Accepted
time: 69ms
memory: 4596kb
Test #21:
score: 0
Accepted
time: 88ms
memory: 4812kb
Test #22:
score: 0
Accepted
time: 92ms
memory: 5764kb
Test #23:
score: 0
Accepted
time: 95ms
memory: 4664kb
Test #24:
score: 0
Accepted
time: 83ms
memory: 5528kb
Test #25:
score: 0
Accepted
time: 98ms
memory: 4608kb
Test #26:
score: 0
Accepted
time: 82ms
memory: 5580kb
Test #27:
score: 0
Accepted
time: 96ms
memory: 4604kb
Test #28:
score: 0
Accepted
time: 87ms
memory: 5560kb
Test #29:
score: 0
Accepted
time: 468ms
memory: 5768kb
Test #30:
score: 0
Accepted
time: 309ms
memory: 5528kb
Test #31:
score: 0
Accepted
time: 94ms
memory: 5764kb
Test #32:
score: 0
Accepted
time: 113ms
memory: 4780kb
Test #33:
score: 0
Accepted
time: 86ms
memory: 5616kb
Test #34:
score: 0
Accepted
time: 132ms
memory: 4780kb
Test #35:
score: 0
Accepted
time: 96ms
memory: 5760kb
Test #36:
score: 0
Accepted
time: 100ms
memory: 5676kb
Test #37:
score: 0
Accepted
time: 225ms
memory: 5664kb
Test #38:
score: 0
Accepted
time: 466ms
memory: 5560kb
Test #39:
score: 0
Accepted
time: 447ms
memory: 5676kb
Test #40:
score: 0
Accepted
time: 413ms
memory: 5556kb
Test #41:
score: 0
Accepted
time: 400ms
memory: 5576kb
Test #42:
score: 0
Accepted
time: 100ms
memory: 5676kb
Test #43:
score: 0
Accepted
time: 103ms
memory: 5764kb
Test #44:
score: 0
Accepted
time: 470ms
memory: 5620kb
Test #45:
score: 0
Accepted
time: 427ms
memory: 5556kb
Test #46:
score: 0
Accepted
time: 398ms
memory: 5556kb
Test #47:
score: 0
Accepted
time: 248ms
memory: 5204kb
Test #48:
score: 0
Accepted
time: 163ms
memory: 4928kb
Test #49:
score: 0
Accepted
time: 400ms
memory: 5524kb
Test #50:
score: 0
Accepted
time: 93ms
memory: 5580kb