QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#485591#2347. Traffic Blightsarnold518WA 5ms9376kbC++141.7kb2024-07-20 20:35:552024-07-20 20:35:55

Judging History

This is the latest submission verdict.

  • [2024-07-20 20:35:55]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 9376kb
  • [2024-07-20 20:35:55]
  • 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]=1;
            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: 3ms
memory: 9372kb

Test #2:

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

Test #3:

score: -100
Wrong Answer
time: 5ms
memory: 9368kb