QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#529325#9220. Bus Analysisucup-team008#AC ✓1025ms4568kbC++1711.5kb2024-08-24 11:58:112024-08-24 11:58:12

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 11:58:12]
  • 评测
  • 测评结果:AC
  • 用时:1025ms
  • 内存:4568kb
  • [2024-08-24 11:58:11]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(0) cerr
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef int64_t ll;

struct barrett_reduction {
    unsigned mod;
    uint64_t div;
 
    barrett_reduction(unsigned m) : mod(m), div(-1LLU / m) {}
 
    unsigned operator()(uint64_t a) const {
#ifdef __SIZEOF_INT128__
        uint64_t q = uint64_t(__uint128_t(div) * a >> 64);
        uint64_t r = a - q * mod;
        return unsigned(r < mod ? r : r - mod);
#endif
        return unsigned(a % mod);
    }
};
 
template<const int &MOD, const barrett_reduction &barrett>
struct _b_int {
    int val;
 
    _b_int(int64_t v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
 
    _b_int(uint64_t v) {
        if (v >= uint64_t(MOD)) v %= MOD;
        val = int(v);
    }
 
    _b_int(int v) : _b_int(int64_t(v)) {}
    _b_int(unsigned v) : _b_int(uint64_t(v)) {}
 
    static int inv_mod(int a, int m = MOD) {
        // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
        int g = m, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const { return val; }
    explicit operator unsigned() const { return val; }
    explicit operator int64_t() const { return val; }
    explicit operator uint64_t() const { return val; }
    explicit operator double() const { return val; }
    explicit operator long double() const { return val; }
 
    _b_int& operator+=(const _b_int &other) {
        val -= MOD - other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    _b_int& operator-=(const _b_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x) {
#if !defined(_WIN32) || defined(_WIN64)
        return barrett(x);
#endif
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * MOD for this to work, so that x / MOD fits in an unsigned 32-bit int.
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
        unsigned quot, rem;
        asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (MOD));
        return rem;
    }
 
    _b_int& operator*=(const _b_int &other) {
        val = fast_mod(uint64_t(val) * other.val);
        return *this;
    }
 
    _b_int& operator/=(const _b_int &other) {
        return *this *= other.inv();
    }
 
    friend _b_int operator+(const _b_int &a, const _b_int &b) { return _b_int(a) += b; }
    friend _b_int operator-(const _b_int &a, const _b_int &b) { return _b_int(a) -= b; }
    friend _b_int operator*(const _b_int &a, const _b_int &b) { return _b_int(a) *= b; }
    friend _b_int operator/(const _b_int &a, const _b_int &b) { return _b_int(a) /= b; }
 
    _b_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    _b_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    _b_int operator++(int) { _b_int before = *this; ++*this; return before; }
    _b_int operator--(int) { _b_int before = *this; --*this; return before; }
 
    _b_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    friend bool operator==(const _b_int &a, const _b_int &b) { return a.val == b.val; }
    friend bool operator!=(const _b_int &a, const _b_int &b) { return a.val != b.val; }
    friend bool operator<(const _b_int &a, const _b_int &b) { return a.val < b.val; }
    friend bool operator>(const _b_int &a, const _b_int &b) { return a.val > b.val; }
    friend bool operator<=(const _b_int &a, const _b_int &b) { return a.val <= b.val; }
    friend bool operator>=(const _b_int &a, const _b_int &b) { return a.val >= b.val; }
 
    _b_int inv() const {
        return inv_mod(val);
    }
 
    _b_int pow(int64_t p) const {
        if (p < 0)
            return inv().pow(-p);
 
        _b_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            p >>= 1;
 
            if (p > 0)
                a *= a;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &os, const _b_int &m) {
        return os << m.val;
    }
 
    friend istream& operator>>(istream &is, _b_int &m) {
        int64_t x;
        is >> x;
        m = x;
        return is;
    }
};
 
int MOD = int(1e9) + 7;
barrett_reduction barrett(MOD);
using mnum = _b_int<MOD, barrett>;

vector<array<int, 4>> allposs;
vector<int> nocheck, check, checkcost;
void rsolve() {
  int src = lb(all(allposs), array<int, 4>({75, 0, 0, 0})) - allposs.begin();
  int n;
  cin >> n;
  vector<int> v(n);
  for(auto& x: v) cin >> x;
  int lhst = -1e9;
  vector<mnum> ways(sz(allposs));
  vector<mnum> sumcost(sz(allposs));
  ways[src] = 1;
  auto propno = [&]() -> void {
    vector<mnum> nways(sz(allposs));
    vector<mnum> nsumcost(sz(allposs));
    for(int i = 0; i < sz(ways); i++) {
      nways[nocheck[i]] += ways[i];
      nsumcost[nocheck[i]] += sumcost[i];
    }
    ways.swap(nways);
    sumcost.swap(nsumcost);
  };
  auto propyes = [&]() -> void {
    vector<mnum> nways(sz(allposs));
    vector<mnum> nsumcost(sz(allposs));
    for(int i = 0; i < sz(ways); i++) {
      nways[nocheck[i]] += ways[i];
      nsumcost[nocheck[i]] += sumcost[i];
      nways[check[i]] += ways[i];
      nsumcost[check[i]] += sumcost[i] + ways[i] * checkcost[i];
    }
    ways.swap(nways);
    sumcost.swap(nsumcost);
  };
  for(int out: v) {
    for(int i = 0; i < min(76, out - lhst - 1); i++) {
      propno();
    }
    propyes();
    lhst = out;
  }
  mnum ret = 0;
  for(auto out: sumcost) ret += out;
  cout << ret << "\n";
}
void precomp() {
  set<array<int, 4>> can; // <#0, #-2, #-4, #-6>
  can.insert({75, 0, 0, 0}); 
  queue<array<int, 4>> q;
  q.push({75, 0, 0, 0});
  while(sz(q)) {
    auto [a, b, c, d] = q.front(); q.pop();
    // do nothing
    {
      int na = a;
      int nb = b;
      int nc = c;
      int nd = d;
      na++;
      if(nd) nd--;
      else if(nc) nc--;
      else if(nb) nb--;
      else na--;
      if(!can.count({na, nb, nc, nd})) {
        can.insert({na, nb, nc, nd});
        q.push({na, nb, nc, nd});
      }
    }
    vector<int> choice;
    for(int i = 0; i < a; i++) choice.pb(0);
    for(int i = 0; i < b; i++) choice.pb(-2);
    for(int i = 0; i < c; i++) choice.pb(-4);
    for(int i = 0; i < d; i++) choice.pb(-6);
    int cand = min(choice[19] + 2, choice[74] + 6);
    assert(cand <= 2);
    assert(cand >= 0);
    if(cand == 2) {
      int na = 1;
      int nb = a;
      int nc = b;
      int nd = c;
      if(na+nb+nc+nd > 75) {
        assert(na+nb+nc+nd == 76);
        if(nd) nd--;
        else if(nc) nc--;
        else if(nb) nb--;
        else na--;
      }
      assert(na+nb+nc+nd == 75); 
      if(!can.count({na, nb, nc, nd})) {
        can.insert({na, nb, nc, nd});
        q.push({na, nb, nc, nd});
      }
    }
  }
  for(auto out: can) allposs.pb(out);
  for(int qq = 0; qq < sz(allposs); qq++) {
    auto [a, b, c, d] = allposs[qq];
    // do nothing
    {
      int na = a;
      int nb = b;
      int nc = c;
      int nd = d;
      na++;
      if(nd) nd--;
      else if(nc) nc--;
      else if(nb) nb--;
      else na--;
      auto idx = lb(all(allposs), array<int, 4>({na, nb, nc, nd})) - allposs.begin();
      nocheck.pb(idx);
    }
    vector<int> choice;
    for(int i = 0; i < a; i++) choice.pb(0);
    for(int i = 0; i < b; i++) choice.pb(-2);
    for(int i = 0; i < c; i++) choice.pb(-4);
    for(int i = 0; i < d; i++) choice.pb(-6);
    int cand = min(choice[19] + 2, choice[74] + 6);
    assert(cand <= 2);
    assert(cand >= 0);
    if(cand == 2) {
      int oldcost = int(a>0) + int(b>0) + int(c>0) + int(d>0);
      int na = 1;
      int nb = a;
      int nc = b;
      int nd = c;
      if(na+nb+nc+nd > 75) {
        assert(na+nb+nc+nd == 76);
        if(nd) nd--;
        else if(nc) nc--;
        else if(nb) nb--;
        else na--;
      }
      assert(na+nb+nc+nd == 75); 
      int newcost = int(na>0) + int(nb>0) + int(nc>0) + int(nd>0);
      assert(newcost >= oldcost);
      auto idx = lb(all(allposs), array<int, 4>({na, nb, nc, nd})) - allposs.begin();
      check.pb(idx);
      checkcost.pb(2);
      //checkcost.pb(2*(newcost-oldcost));
    }
    else {
      check.pb(nocheck.back());
      checkcost.pb(0);
    }
  }
}
void solve() {
  precomp();
  rsolve();
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

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

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 4292kb

input:

3
1 8 20

output:

14

result:

ok 1 number(s): "14"

Test #2:

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

input:

5
25 45 65 85 1000000000

output:

156

result:

ok 1 number(s): "156"

Test #3:

score: 0
Accepted
time: 73ms
memory: 4432kb

input:

1000
2 7 9 12 14 17 18 21 22 28 29 33 34 35 37 38 44 45 46 50 58 59 63 66 71 72 75 76 77 78 80 81 83 84 87 92 100 101 107 108 109 112 114 116 118 123 124 131 142 143 144 145 148 150 151 152 153 155 157 158 165 167 168 169 171 176 182 185 190 192 198 202 204 205 212 213 223 224 225 226 229 231 240 24...

output:

932594593

result:

ok 1 number(s): "932594593"

Test #4:

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

input:

200
1 2 4 9 10 11 12 15 16 17 18 19 22 24 27 28 33 36 37 39 43 44 45 47 48 49 50 51 52 56 60 61 62 63 68 70 71 72 73 74 78 80 81 84 86 92 93 98 99 100 102 105 107 108 110 111 114 115 116 122 123 125 129 132 133 135 137 138 139 141 142 143 144 149 150 151 152 153 154 155 159 160 165 171 172 174 176 1...

output:

422301620

result:

ok 1 number(s): "422301620"

Test #5:

score: 0
Accepted
time: 342ms
memory: 4204kb

input:

1000
999975020 999975030 999975050 999975056 999975085 999975118 999975207 999975213 999975240 999975307 999975332 999975344 999975356 999975384 999975405 999975468 999975499 999975558 999975559 999975571 999975631 999975664 999975680 999975689 999975731 999975738 999975765 999975831 999975838 99997...

output:

335758758

result:

ok 1 number(s): "335758758"

Test #6:

score: 0
Accepted
time: 9ms
memory: 4256kb

input:

3
1 8 20

output:

14

result:

ok 1 number(s): "14"

Test #7:

score: 0
Accepted
time: 649ms
memory: 4324kb

input:

1000
214 216 381 497 539 645 772 927 1211 1238 1239 1298 1403 1426 1437 1504 1515 1648 1800 1816 1946 2008 2038 2066 2144 2173 2236 2253 2291 2574 2632 2643 2658 2671 2689 2886 2910 2948 3002 3033 3039 3057 3077 3188 3240 3322 3331 3449 3467 3578 3730 3796 3897 3973 4152 4160 4199 4331 4386 4429 465...

output:

877690181

result:

ok 1 number(s): "877690181"

Test #8:

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

input:

1
963837006

output:

2

result:

ok 1 number(s): "2"

Test #9:

score: 0
Accepted
time: 585ms
memory: 4568kb

input:

999
17 234 337 379 449 607 646 703 716 878 887 898 901 942 964 1075 1198 1356 1432 1546 1547 1619 1668 1769 1818 1826 1881 1900 1960 2017 2088 2266 2273 2339 2376 2377 2396 2399 2438 2461 2484 2567 2620 2661 2680 2791 2881 3040 3081 3082 3094 3102 3205 3218 3225 3227 3239 3250 3331 3393 3425 3530 35...

output:

651884156

result:

ok 1 number(s): "651884156"

Test #10:

score: 0
Accepted
time: 42ms
memory: 4556kb

input:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

754964156

result:

ok 1 number(s): "754964156"

Test #11:

score: 0
Accepted
time: 89ms
memory: 4260kb

input:

1000
1 2 5 12 13 16 19 21 24 40 42 50 51 54 60 61 63 65 69 72 83 100 106 117 121 122 132 133 135 144 149 154 156 157 158 159 163 172 187 190 194 195 196 200 204 221 224 225 236 237 238 239 242 248 250 251 257 258 264 269 272 279 284 286 288 294 298 301 303 322 324 326 328 347 348 358 363 367 368 376...

output:

736216287

result:

ok 1 number(s): "736216287"

Test #12:

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

input:

10
2 5 8 10 11 15 20 32 34 48

output:

3806

result:

ok 1 number(s): "3806"

Test #13:

score: 0
Accepted
time: 1025ms
memory: 4484kb

input:

1000
3092896 4096697 4935574 5665657 6717242 12350017 13784643 14890236 15103239 16083201 16158442 17406219 18377269 19146618 20149007 20444388 20799716 21703919 22502750 26066931 27425220 27610093 30584293 30942406 33020849 33381138 34889813 35505301 35711460 36618608 37636454 42073851 43834284 441...

output:

423205184

result:

ok 1 number(s): "423205184"

Test #14:

score: 0
Accepted
time: 46ms
memory: 4256kb

input:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 101 10...

output:

167925937

result:

ok 1 number(s): "167925937"

Test #15:

score: 0
Accepted
time: 285ms
memory: 4264kb

input:

1000
123123123 123123143 123123163 123123183 123123203 123123223 123123243 123123263 123123283 123123303 123123323 123123343 123123363 123123383 123123403 123123423 123123443 123123463 123123483 123123503 123123523 123123543 123123563 123123583 123123603 123123623 123123643 123123663 123123683 12312...

output:

152353232

result:

ok 1 number(s): "152353232"

Test #16:

score: 0
Accepted
time: 11ms
memory: 4516kb

input:

5
25 45 65 85 1000000000

output:

156

result:

ok 1 number(s): "156"

Test #17:

score: 0
Accepted
time: 48ms
memory: 4260kb

input:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 79 80 81 82 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 103 104 105...

output:

506306982

result:

ok 1 number(s): "506306982"

Test #18:

score: 0
Accepted
time: 150ms
memory: 4552kb

input:

1000
6 15 22 23 29 36 55 56 63 75 84 98 100 107 114 119 124 126 135 150 155 156 158 159 162 168 179 180 193 196 197 202 204 214 215 218 229 242 244 248 251 253 255 265 271 273 286 288 302 306 324 334 368 380 388 409 425 473 476 489 525 526 534 540 554 556 562 566 570 573 574 592 621 636 640 645 653 ...

output:

272405461

result:

ok 1 number(s): "272405461"

Test #19:

score: 0
Accepted
time: 11ms
memory: 4260kb

input:

19
999999810 999999814 999999829 999999838 999999839 999999843 999999849 999999853 999999883 999999889 999999896 999999907 999999911 999999925 999999926 999999946 999999957 999999987 999999993

output:

5337088

result:

ok 1 number(s): "5337088"

Test #20:

score: 0
Accepted
time: 45ms
memory: 4332kb

input:

999
1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 27 28 29 30 31 32 33 34 35 38 39 40 41 42 43 45 46 47 49 50 51 52 54 55 56 57 59 60 61 62 64 65 66 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 85 86 88 89 90 91 92 93 94 95 96 97 99 100 101 103 105 106 107 108 109 110 111 112 11...

output:

571215215

result:

ok 1 number(s): "571215215"

Test #21:

score: 0
Accepted
time: 59ms
memory: 4320kb

input:

1000
123121000 123121001 123121002 123121005 123121012 123121013 123121018 123121020 123121021 123121024 123121028 123121029 123121031 123121034 123121035 123121036 123121037 123121038 123121043 123121044 123121045 123121046 123121047 123121048 123121050 123121051 123121052 123121055 123121057 12312...

output:

250442238

result:

ok 1 number(s): "250442238"

Extra Test:

score: 0
Extra Test Passed