QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485592#2347. Traffic Blightsarnold518AC ✓311ms9492kbC++141.7kb2024-07-20 20:42:232024-07-20 20:42:23

Judging History

This is the latest submission verdict.

  • [2024-07-20 20:42:23]
  • Judged
  • Verdict: AC
  • Time: 311ms
  • Memory: 9492kb
  • [2024-07-20 20:42:23]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int X = 2520;

int N;
int A[MAXN+10][3], B[110];
bitset<110> P[X+10][110];
double Q2[X+10];
int Q[X+10][110];

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    B[1]=1;
    vector<int> V;
    for(int i=1; i<=100; i++)
    {
        int m=i/__gcd(i, X);
        if(m==1) continue;
        V.push_back(m);
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for(auto m : V)
    {
        B[m]=m;
        for(int j=2; j<m; j++) if(m%j==0 && B[j]!=0) B[j]=m;
    }

    for(int i=0; i<X; i++)
    {
        Q2[i]=1;
        P[i][1][0]=1; Q[i][1]=1;
        for(auto m : V)
        {
            Q[i][m]=m;
            for(int j=0; j<m; j++) P[i][m][j]=1;
        }
    }

    // for(int i=1; i<=100; i++) if(B[i]) printf("%d : %d\n", i, B[i]);

    scanf("%d", &N);
    for(int i=1; i<=N; i++) scanf("%d%d%d", &A[i][0], &A[i][1], &A[i][2]);

    double bef=1;
    for(int i=1; i<=N; i++)
    {
        int x=A[i][0], r=A[i][1], g=A[i][2];
        int m=r+g;
        int m2=B[m/__gcd(m, X)];

        for(int j=0; j<X; j++) if(Q[j][m2]) Q2[j]/=(double)Q[j][m2]/m2;
        for(int t=0; t<m2*X; t++) P[t%X][m2][t/X]=(P[t%X][m2][t/X] & ((t+x)%m>=r));
        for(int j=0; j<X; j++) Q[j][m2]=P[j][m2].count();
        for(int j=0; j<X; j++) Q2[j]*=(double)Q[j][m2]/m2;

        double now=0;
        for(int j=0; j<X; j++) now+=Q2[j];
        now/=X;
        printf("%.20lf\n", bef-now);
        bef=now;
    }
    printf("%.20lf\n", bef);
}

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 9312kb

Test #2:

score: 0
Accepted
time: 2ms
memory: 9344kb

Test #3:

score: 0
Accepted
time: 2ms
memory: 9160kb

Test #4:

score: 0
Accepted
time: 2ms
memory: 9176kb

Test #5:

score: 0
Accepted
time: 2ms
memory: 9444kb

Test #6:

score: 0
Accepted
time: 5ms
memory: 9172kb

Test #7:

score: 0
Accepted
time: 5ms
memory: 9172kb

Test #8:

score: 0
Accepted
time: 2ms
memory: 9160kb

Test #9:

score: 0
Accepted
time: 2ms
memory: 9492kb

Test #10:

score: 0
Accepted
time: 6ms
memory: 9176kb

Test #11:

score: 0
Accepted
time: 5ms
memory: 9172kb

Test #12:

score: 0
Accepted
time: 7ms
memory: 9384kb

Test #13:

score: 0
Accepted
time: 4ms
memory: 9416kb

Test #14:

score: 0
Accepted
time: 4ms
memory: 9372kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 9168kb

Test #16:

score: 0
Accepted
time: 6ms
memory: 9312kb

Test #17:

score: 0
Accepted
time: 12ms
memory: 9488kb

Test #18:

score: 0
Accepted
time: 10ms
memory: 9344kb

Test #19:

score: 0
Accepted
time: 13ms
memory: 9172kb

Test #20:

score: 0
Accepted
time: 5ms
memory: 9376kb

Test #21:

score: 0
Accepted
time: 7ms
memory: 9368kb

Test #22:

score: 0
Accepted
time: 32ms
memory: 9440kb

Test #23:

score: 0
Accepted
time: 6ms
memory: 9248kb

Test #24:

score: 0
Accepted
time: 34ms
memory: 9480kb

Test #25:

score: 0
Accepted
time: 3ms
memory: 9172kb

Test #26:

score: 0
Accepted
time: 26ms
memory: 9180kb

Test #27:

score: 0
Accepted
time: 6ms
memory: 9308kb

Test #28:

score: 0
Accepted
time: 32ms
memory: 9376kb

Test #29:

score: 0
Accepted
time: 301ms
memory: 9376kb

Test #30:

score: 0
Accepted
time: 152ms
memory: 9344kb

Test #31:

score: 0
Accepted
time: 18ms
memory: 9244kb

Test #32:

score: 0
Accepted
time: 20ms
memory: 9420kb

Test #33:

score: 0
Accepted
time: 31ms
memory: 9308kb

Test #34:

score: 0
Accepted
time: 30ms
memory: 9252kb

Test #35:

score: 0
Accepted
time: 83ms
memory: 9320kb

Test #36:

score: 0
Accepted
time: 78ms
memory: 9240kb

Test #37:

score: 0
Accepted
time: 127ms
memory: 9416kb

Test #38:

score: 0
Accepted
time: 311ms
memory: 9368kb

Test #39:

score: 0
Accepted
time: 268ms
memory: 9164kb

Test #40:

score: 0
Accepted
time: 268ms
memory: 9344kb

Test #41:

score: 0
Accepted
time: 232ms
memory: 9240kb

Test #42:

score: 0
Accepted
time: 19ms
memory: 9348kb

Test #43:

score: 0
Accepted
time: 28ms
memory: 9440kb

Test #44:

score: 0
Accepted
time: 243ms
memory: 9488kb

Test #45:

score: 0
Accepted
time: 235ms
memory: 9344kb

Test #46:

score: 0
Accepted
time: 230ms
memory: 9416kb

Test #47:

score: 0
Accepted
time: 119ms
memory: 9396kb

Test #48:

score: 0
Accepted
time: 63ms
memory: 9160kb

Test #49:

score: 0
Accepted
time: 240ms
memory: 9316kb

Test #50:

score: 0
Accepted
time: 27ms
memory: 9484kb