oj.uz

Submission #1003406

# Submission time Handle Problem Language Result Execution time Memory
1003406 2024-06-20T09:54:34 Z vjudge1 Party (INOI20_party) C++17
7 / 100
 3000 ms 516 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
 
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;
ll n;
ll freq[20];
ll binpow(ll n, ll p)
{
    ll ans = 1;
    while (p)
    {
        ans = (p & 1 ? (ans * n) % mod : ans);
        n = (n * n) % mod;
        p >>= 1;
    }
    return ans;
}
ll inv(ll x)
{
    return binpow(x, mod - 2);
}
void dfs(ll v, ll par = 0, ll depth = 0)
{
    freq[depth]++;
    for (ll to : {v >> 1, v * 2, v * 2 + 1}) if (to != par and to <= n and to >= 1) dfs(to, v, depth + 1);
}
void solve()
{
    cin >> n;
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 0; j < 20; j++) freq[j] = 0;
        dfs(i);
        ll cur = 0;
        for (ll j = 19; j >= 0; j--)
            ans = (ans + binpow(2, cur) * (binpow(2, freq[j]) - 1) % mod * j % mod) % mod, cur += freq[j];
    }
    ans = ans * inv(binpow(2, n) - 1 + mod) % mod;;
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 7 ms 516 KB Output is correct
11 Correct 264 ms 452 KB Output is correct
12 Correct 269 ms 460 KB Output is correct
13 Correct 321 ms 348 KB Output is correct
14 Correct 241 ms 444 KB Output is correct
15 Correct 254 ms 452 KB Output is correct
16 Correct 273 ms 460 KB Output is correct
17 Correct 154 ms 344 KB Output is correct
18 Correct 166 ms 344 KB Output is correct
19 Correct 166 ms 344 KB Output is correct
20 Correct 159 ms 444 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3028 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 7 ms 516 KB Output is correct
11 Correct 264 ms 452 KB Output is correct
12 Correct 269 ms 460 KB Output is correct
13 Correct 321 ms 348 KB Output is correct
14 Correct 241 ms 444 KB Output is correct
15 Correct 254 ms 452 KB Output is correct
16 Correct 273 ms 460 KB Output is correct
17 Correct 154 ms 344 KB Output is correct
18 Correct 166 ms 344 KB Output is correct
19 Correct 166 ms 344 KB Output is correct
20 Correct 159 ms 444 KB Output is correct
21 Execution timed out 3028 ms 344 KB Time limit exceeded
22 Halted 0 ms 0 KB -