oj.uz

Submission #633699

# Submission time Handle Problem Language Result Execution time Memory
633699 2022-08-23T05:39:36 Z 406 Party (INOI20_party) C++17
40 / 100
 3000 ms 1018204 KB 
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

#define forn(a, b) for (int a = 0; a < (b); a++)
#define rofn(a, b) for (int a = (b) - 1; a >= 0; a--)
#define LOG(a) (63 - __builtin_clzll(a))
#define chmx(a, b) a = max(a, b)
#define chmn(a, b) a = min(a, b)
#define pb push_back
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1,*p2;

/*inline int read() {
	ll x = 0, f = 1; char c;
	while(!isdigit(c = gc())) if(c=='-') f=-1;
	while(isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = gc();
	return x * f;
}
*/
const ll INFL = 1ll << 60;
const int INF = 1 << 29;
const int N = 62;
const int M = 2 * N;
const int MOD = 1e9 + 7;
const int X = 2.6e8;

ll d[2][M][M], n;
int ptr, ans, q;
int pw2[X + 1];


ll pw(ll a, ll b) {
    b %= (MOD - 1);
    ll re = 1;
    while (b) {
        if (b & 1)
            re = (re * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return re;
}

ll p2(ll b) {
    b %= (MOD - 1);
    ll a = 1;
    while (b > X) {
        a = (a * pw2[X]) % MOD;
        b -= X;
    }
    a *= pw2[b];
    return a % MOD;
}

void calc_dist(ll v, ll sub, int lg) {
    for (int k = lg; k < 62; k++) {
        int x = k - lg;
        if ((v << x) > n)
            d[1][ptr][x] = 0;
        else
            d[1][ptr][x] = min(n - (v << x) + 1, ((ll)1 << x));
    }
    if (v > 1) {
        for (int k = 2; k < N + 2; k++)
            d[0][ptr][k] -= d[1][ptr][k - 2];
    }
}

void pass() {
    for (int k = 1; k < M; k++)
        d[0][ptr + 1][k] = d[0][ptr][k - 1] + d[1][ptr][k - 1];
    ptr++;
}

void Complete(ll v, ll sub, int lg) {
    if (v > n) {
        ptr--;
        return;
    }
    //cout << "C: " << v << ' ' << sub << " PTR: " << ptr << '\n';
    calc_dist(v, sub, lg);

    pass();
    Complete(v << 1, sub >> 1, lg + 1);
    q <<= 1;
    if (q >= MOD)
        q -= MOD;

    ll s = 0;
    for (int k = 0; s != n; k++) {
        s += d[0][ptr][k] + d[1][ptr][k];
        q += p2(n - s) - 1;
        if (q >= MOD)
            q -= MOD;
    }
    ptr--;
}

void F(ll v, ll sub, int lg) {
    if (v > n) {
        ptr--;
        return;
    }

    //cout << "F: " << v << ' ' << sub << " PTR: " << ptr << '\n';
    calc_dist(v, sub, lg);

    ll r = (v << 1) | 1;
    ll l = (v << 1);
    int cntr = 0, cntl = 0;
    
    while (r <= n)
        r <<= 1, cntr++;
    while (l <= n)
        l <<= 1, cntl++;

    if (cntr == cntl) {
        q = 0;
        pass();
        Complete(v << 1, (1ll << cntl) - 1, lg + 1);
        ans += q;
        ans %= MOD;

        pass();
        F((v << 1) | 1, sub - (1ll << cntl), lg + 1);
    }
    else {
        q = 0;
        pass();
        Complete((v << 1) | 1, (1ll << cntr) - 1,lg + 1);

        ans += q;
        if (ans >= MOD)
            ans -= MOD;

        pass();
        F((v << 1), sub - (1ll << cntr), lg + 1);
    }
    

    ll s = 0;
    for (int k = 0; s != n; k++) {
        s += d[0][ptr][k] + d[1][ptr][k];
        ans += p2(n - s) - 1;
        if (ans >= MOD)
            ans -= MOD;
    }
    ptr--;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    pw2[0] = 1;
    for (int i = 1; i <= X; i++) {
        pw2[i] = pw2[i - 1] * 2;
        if (pw2[i] >= MOD)
            pw2[i] -= MOD;
    }

    int query;
    cin >> query;
    while (query--) {
        cin >> n;

        F(1, n, 1);
        ll re = pw(2, n) - 1;

        ans = (ans * pw(re, MOD - 2)) % MOD;
        cout << ans << '\n';

        ans = q = ptr = 0;
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1300 ms 1017984 KB Output is correct
2 Correct 1288 ms 1018068 KB Output is correct
3 Correct 1304 ms 1017892 KB Output is correct
4 Correct 1300 ms 1017908 KB Output is correct
5 Correct 1341 ms 1017956 KB Output is correct
6 Correct 1317 ms 1017924 KB Output is correct
7 Correct 1306 ms 1017964 KB Output is correct
8 Correct 1303 ms 1017904 KB Output is correct
9 Correct 1305 ms 1017852 KB Output is correct
10 Correct 1314 ms 1017896 KB Output is correct
11 Correct 1280 ms 1017852 KB Output is correct
12 Correct 1295 ms 1017980 KB Output is correct
13 Correct 1339 ms 1017908 KB Output is correct
14 Correct 1446 ms 1017860 KB Output is correct
15 Correct 1360 ms 1017996 KB Output is correct
16 Correct 1315 ms 1017840 KB Output is correct
17 Correct 1325 ms 1017964 KB Output is correct
18 Correct 1358 ms 1017880 KB Output is correct
19 Correct 1347 ms 1017988 KB Output is correct
20 Correct 1329 ms 1017900 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1396 ms 1018056 KB Output is correct
2 Correct 1405 ms 1018036 KB Output is correct
3 Correct 1395 ms 1017996 KB Output is correct
4 Correct 1429 ms 1018092 KB Output is correct
5 Correct 1406 ms 1018004 KB Output is correct
6 Correct 1415 ms 1018116 KB Output is correct
7 Correct 1441 ms 1017992 KB Output is correct
8 Correct 1384 ms 1018028 KB Output is correct
9 Correct 1395 ms 1018048 KB Output is correct
10 Correct 1399 ms 1018104 KB Output is correct
11 Execution timed out 3120 ms 1018072 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1410 ms 1018044 KB Output is correct
2 Correct 1403 ms 1018076 KB Output is correct
3 Correct 1602 ms 1018164 KB Output is correct
4 Correct 1401 ms 1018160 KB Output is correct
5 Correct 1394 ms 1018124 KB Output is correct
6 Correct 1407 ms 1018100 KB Output is correct
7 Correct 1407 ms 1018060 KB Output is correct
8 Correct 1426 ms 1018196 KB Output is correct
9 Correct 1410 ms 1018068 KB Output is correct
10 Correct 1403 ms 1018036 KB Output is correct
11 Correct 1723 ms 1018064 KB Output is correct
12 Correct 1678 ms 1018204 KB Output is correct
13 Correct 1696 ms 1018048 KB Output is correct
14 Correct 1682 ms 1018040 KB Output is correct
15 Correct 1711 ms 1018056 KB Output is correct
16 Correct 1697 ms 1017964 KB Output is correct
17 Correct 1701 ms 1018144 KB Output is correct
18 Correct 1675 ms 1018040 KB Output is correct
19 Correct 1684 ms 1018092 KB Output is correct
20 Correct 1639 ms 1017996 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1300 ms 1017984 KB Output is correct
2 Correct 1288 ms 1018068 KB Output is correct
3 Correct 1304 ms 1017892 KB Output is correct
4 Correct 1300 ms 1017908 KB Output is correct
5 Correct 1341 ms 1017956 KB Output is correct
6 Correct 1317 ms 1017924 KB Output is correct
7 Correct 1306 ms 1017964 KB Output is correct
8 Correct 1303 ms 1017904 KB Output is correct
9 Correct 1305 ms 1017852 KB Output is correct
10 Correct 1314 ms 1017896 KB Output is correct
11 Correct 1280 ms 1017852 KB Output is correct
12 Correct 1295 ms 1017980 KB Output is correct
13 Correct 1339 ms 1017908 KB Output is correct
14 Correct 1446 ms 1017860 KB Output is correct
15 Correct 1360 ms 1017996 KB Output is correct
16 Correct 1315 ms 1017840 KB Output is correct
17 Correct 1325 ms 1017964 KB Output is correct
18 Correct 1358 ms 1017880 KB Output is correct
19 Correct 1347 ms 1017988 KB Output is correct
20 Correct 1329 ms 1017900 KB Output is correct
21 Correct 1396 ms 1018056 KB Output is correct
22 Correct 1405 ms 1018036 KB Output is correct
23 Correct 1395 ms 1017996 KB Output is correct
24 Correct 1429 ms 1018092 KB Output is correct
25 Correct 1406 ms 1018004 KB Output is correct
26 Correct 1415 ms 1018116 KB Output is correct
27 Correct 1441 ms 1017992 KB Output is correct
28 Correct 1384 ms 1018028 KB Output is correct
29 Correct 1395 ms 1018048 KB Output is correct
30 Correct 1399 ms 1018104 KB Output is correct
31 Execution timed out 3120 ms 1018072 KB Time limit exceeded
32 Halted 0 ms 0 KB -