QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#485591 | #2347. Traffic Blights | arnold518 | WA | 5ms | 9376kb | C++14 | 1.7kb | 2024-07-20 20:35:55 | 2024-07-20 20:35:55 |
Judging History
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