QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641872#2347. Traffic BlightsElegiaAC ✓333ms5424kbC++233.7kb2024-10-15 03:02:562024-10-15 03:02:57

Judging History

This is the latest submission verdict.

  • [2024-10-15 03:02:57]
  • Judged
  • Verdict: AC
  • Time: 333ms
  • Memory: 5424kb
  • [2024-10-15 03:02:56]
  • Submitted

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