QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641872 | #2347. Traffic Blights | Elegia | AC ✓ | 333ms | 5424kb | C++23 | 3.7kb | 2024-10-15 03:02:56 | 2024-10-15 03:02:57 |
Judging History
answer
/*
_/_/_/_/ _/_/_/_/_/ _/_/_/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/_/
_/_/_/_/ _/_/ _/_/_/_/_/
_/_/_/_/ _/ _/ _/ _/
_/ _/ _/ _/ _/_/ _/_/
_/ _/ _/_/ _/ _/_/ _/
_/ _/ _/ _/ _/ _/
_/ _/ _/_/ _/ _/
_/ _/ _/ _/ _/ _/
_/_/_/_/ _/ _/ _/ _/
_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/ _/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/_/_/_/_/ _/_/_/_/_/
_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/ _/_/_/_/
_/ _/ _/
_/ _/ _/
_/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &x : v)
is >> x;
return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
if (!v.empty()) {
os << v.front();
for (int i = 1; i < v.size(); ++i)
os << ' ' << v[i];
}
return os;
}
const int N = 510, L = 2520, R = 100;
const double MIN = numeric_limits<double>::min();
int n;
int x[N], r[N], g[N];
double f[N];
int pc;
int p[R + 1], pk[R + 1], vis[R + 1], id[R + 1];
bitset<R> bs[L][30];
double pr[L];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
#ifdef ELEGIA
freopen("test.in", "r", stdin);
int nol_cl = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x[i] >> r[i] >> g[i];
x[i] %= r[i] + g[i];
}
for (int i = 2; i <= R; ++i) {
if (!vis[i]) {
id[i] = pc;
p[pc] = i;
pk[pc] = 1;
while (pk[pc] * i <= R) pk[pc] *= i;
++pc;
for (int j = i; j <= R; j += i) vis[j] = i;
}
}
for (int i = 1; i <= n; ++i) {
int per = r[i] + g[i];
int banL = per - x[i], banR = banL + r[i];
int gc = gcd(per, L), sub = per / gc;
if (sub == 1) {
for (int j = banL; j != banR; ++j)
for (int k = 0; k != L; k += gc)
pr[j % gc + k] = MIN;
} else {
int d = id[vis[sub]];
for (int j = banL; j != banR; ++j) {
for (int k = 0; k != L; k += gc) {
int pos = j % gc + k;
if (pr[pos] == MIN) continue;
pr[pos] += log(pk[d] - bs[pos][d].count());
int u = 0;
while ((u * L + pos - j) % per) ++u;
for (int t = 0; t != pk[d]; t += sub)
bs[pos][d].set(u + t);
if (bs[pos][d].count() == pk[d]) pr[pos] = MIN;
else pr[pos] -= log(pk[d] - bs[pos][d].count());
}
}
}
for (int j = 0; j != L; ++j)
if (pr[j] != MIN) f[i] += exp(-pr[j]);
f[i] /= L;
}
f[0] = 1;
cout << fixed << setprecision(10);
for (int i = 1; i <= n + 1; ++i) cout << f[i - 1] - f[i] << '\n';
#ifdef ELEGIA
LOG("Time: %dms\n", int ((clock()
-nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3964kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 5424kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 4032kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 4744kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 5208kb
Test #8:
score: 0
Accepted
time: 2ms
memory: 5312kb
Test #9:
score: 0
Accepted
time: 9ms
memory: 5284kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 4532kb
Test #11:
score: 0
Accepted
time: 2ms
memory: 5268kb
Test #12:
score: 0
Accepted
time: 4ms
memory: 5316kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 5208kb
Test #14:
score: 0
Accepted
time: 4ms
memory: 5304kb
Test #15:
score: 0
Accepted
time: 25ms
memory: 5340kb
Test #16:
score: 0
Accepted
time: 4ms
memory: 5304kb
Test #17:
score: 0
Accepted
time: 3ms
memory: 5288kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 5156kb
Test #19:
score: 0
Accepted
time: 18ms
memory: 5192kb
Test #20:
score: 0
Accepted
time: 4ms
memory: 5136kb
Test #21:
score: 0
Accepted
time: 1ms
memory: 5252kb
Test #22:
score: 0
Accepted
time: 2ms
memory: 5280kb
Test #23:
score: 0
Accepted
time: 1ms
memory: 5296kb
Test #24:
score: 0
Accepted
time: 0ms
memory: 5332kb
Test #25:
score: 0
Accepted
time: 1ms
memory: 5204kb
Test #26:
score: 0
Accepted
time: 2ms
memory: 5308kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 5244kb
Test #28:
score: 0
Accepted
time: 3ms
memory: 5412kb
Test #29:
score: 0
Accepted
time: 118ms
memory: 5280kb
Test #30:
score: 0
Accepted
time: 34ms
memory: 5320kb
Test #31:
score: 0
Accepted
time: 2ms
memory: 3924kb
Test #32:
score: 0
Accepted
time: 8ms
memory: 3972kb
Test #33:
score: 0
Accepted
time: 9ms
memory: 5184kb
Test #34:
score: 0
Accepted
time: 8ms
memory: 4064kb
Test #35:
score: 0
Accepted
time: 21ms
memory: 5336kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 5248kb
Test #37:
score: 0
Accepted
time: 34ms
memory: 5316kb
Test #38:
score: 0
Accepted
time: 116ms
memory: 5272kb
Test #39:
score: 0
Accepted
time: 105ms
memory: 5404kb
Test #40:
score: 0
Accepted
time: 103ms
memory: 5332kb
Test #41:
score: 0
Accepted
time: 91ms
memory: 5336kb
Test #42:
score: 0
Accepted
time: 2ms
memory: 5268kb
Test #43:
score: 0
Accepted
time: 0ms
memory: 5348kb
Test #44:
score: 0
Accepted
time: 333ms
memory: 5340kb
Test #45:
score: 0
Accepted
time: 266ms
memory: 5404kb
Test #46:
score: 0
Accepted
time: 84ms
memory: 5276kb
Test #47:
score: 0
Accepted
time: 41ms
memory: 5204kb
Test #48:
score: 0
Accepted
time: 23ms
memory: 5280kb
Test #49:
score: 0
Accepted
time: 93ms
memory: 5308kb
Test #50:
score: 0
Accepted
time: 18ms
memory: 5212kb