oj.uz

Submission #966589

# Submission time Handle Problem Language Result Execution time Memory
966589 2024-04-20T05:45:08 Z manizare Party (INOI20_party) C++14
23 / 100
 3000 ms 600 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;

int po(int a,int b){
    if(b==0)return 1 ;
    int v =po(a,b/2); 
    v=v *v % mod ;
    if(b&1) v= v*a % mod;
    return v; 
}
int k ; 
int ch(int x ,int d){
    if(d==-1)return 0;
    d = min(d , k-x-1);
    return ((1ll<<(d+1))-1);
}
int ANS[maxn] ;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    int t ;
    cin >> t ;
    while(t--){
        int n ;
        cin >> n ;
        n++ ;
        k = 0 ; int T =1 ;
        while(T !=n){
            T*=2 ;
            k++;
        } 
        n--;
        if(ANS[k]!=0){
            cout << ANS[k] << "\n";
            continue ;
        }
        int o= 0 ;
        rep(i , 0 , k-1){
            rep(d , 0 , 2*k+2){
                int ans = ch(i , d) ;
                int x = i-1 , D = d-1 ;
                while(x!=-1 && D!=-1){
                    ans++ ;
                    ans = (ans + ch(x+1 , D-1));
                    D--;
                    x--;
                }
                o = (o + (po(2 ,(n-ans))-1+mod)*po(2 , i)%mod + mod)%mod ;
            }
        }
        ANS[k] =o*po(po(2,n)-1+mod, mod-2)%mod;
        cout << o*po(po(2,n)-1+mod, mod-2)%mod << "\n"; 
    }
    return 0 ;
}
/*


*/

Subtask #1
0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 544 KB Output is correct
2 Correct 36 ms 344 KB Output is correct
3 Correct 36 ms 344 KB Output is correct
4 Correct 36 ms 444 KB Output is correct
5 Correct 37 ms 460 KB Output is correct
6 Correct 36 ms 344 KB Output is correct
7 Correct 34 ms 344 KB Output is correct
8 Correct 36 ms 348 KB Output is correct
9 Correct 37 ms 460 KB Output is correct
10 Correct 34 ms 344 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 3 ms 476 KB Output is correct
16 Correct 3 ms 348 KB Output is correct
17 Correct 3 ms 344 KB Output is correct
18 Correct 3 ms 348 KB Output is correct
19 Correct 3 ms 348 KB Output is correct
20 Correct 3 ms 348 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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