QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#83685#2347. Traffic Blightslittle_sunAC ✓470ms5768kbC++141.8kb2023-03-03 02:34:082023-03-03 02:34:08

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-03 02:34:08]
  • Judged
  • Verdict: AC
  • Time: 470ms
  • Memory: 5768kb
  • [2023-03-03 02:34:08]
  • Submitted

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;
}

Details

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