oj.uz

Submission #469028

# Submission time Handle Problem Language Result Execution time Memory
469028 2021-08-30T12:15:23 Z Millad Party (INOI20_party) C++14
7 / 100
 495 ms 412 KB 
// In the name of god
#include <bits/stdc++.h>
     
#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " : " << x << '\n'
     
using namespace std;
 typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
     
const ll maxn = 205;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll ans[maxn], PW[maxn], PW2[maxn], dis[maxn], pw2[maxn], cnt[maxn];
vector <ll> adj[maxn];
ll pw(ll A, ll B){
	ll RES = 1;
	while(B){
		if(B % 2ll)RES = (RES * A) % mod;
		B /= 2ll; A = (A * A) % mod;
	}
	return RES;
}
bool mrk[maxn];
void find_dis(ll v, ll n){
	for(ll i = 1; i <= n; i ++){
		dis[i] = inf;
		cnt[i] = 0; mrk[i] = 0;
	}
	dis[v] = 0; cnt[0] = 0;
	queue<ll> q; q.push(v);
	while(q.size()){
		ll u = q.front(); q.pop();
		if(mrk[u])continue;
		mrk[u] = 1; cnt[dis[u]] ++;
		for(ll j : adj[u]){
			if(dis[j] > dis[u] + 1ll){
				dis[j] = dis[u] + 1ll;
				q.push(j);
			}
		}
	}
}
ll solve(ll n){
       	for(ll i = 1; i <= n; i ++)adj[i].clear();
	for(ll i = 1; i <= n; i ++){
		if(i / 2ll)adj[i].pb(i / 2ll);
		if(i + i <= n)adj[i].pb(i + i);
		if(i + i + 1 <= n)adj[i].pb(i + i + 1);
	}
	ll sum = 0;
	for(ll i = 1; i <= n; i ++){
		find_dis(i, n);
		ll CNT = 0;
		for(ll j = 0; j < n; j ++){
			sum = (sum + (((pw2[n - CNT] - 1ll + mod) % mod) - ((pw2[n - CNT - cnt[j]] - 1ll + mod) % mod) + mod) * pw((pw2[n] - 1ll + mod) % mod, mod - 2) % mod * j % mod) % mod;
			CNT += cnt[j];
		}
	}
	return sum;
}	
int main(){
	pw2[0] = 1;
	for(ll i = 1; i < maxn; i ++)pw2[i] = (pw2[i - 1] * 2ll) % mod;
	for(ll i = 2; i < 201; i ++)ans[i] = solve(i);
	ll q; cin >> q;
	while(q --){
		ll n; cin >> n;
		cout << ans[n] << endl;
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 280 KB Output is correct
2 Correct 495 ms 292 KB Output is correct
3 Correct 487 ms 284 KB Output is correct
4 Correct 480 ms 288 KB Output is correct
5 Correct 481 ms 284 KB Output is correct
6 Correct 479 ms 292 KB Output is correct
7 Correct 475 ms 300 KB Output is correct
8 Correct 470 ms 288 KB Output is correct
9 Correct 477 ms 300 KB Output is correct
10 Correct 482 ms 288 KB Output is correct
11 Correct 490 ms 280 KB Output is correct
12 Correct 481 ms 288 KB Output is correct
13 Correct 476 ms 312 KB Output is correct
14 Correct 486 ms 292 KB Output is correct
15 Correct 475 ms 308 KB Output is correct
16 Correct 475 ms 280 KB Output is correct
17 Correct 471 ms 288 KB Output is correct
18 Correct 474 ms 308 KB Output is correct
19 Correct 477 ms 288 KB Output is correct
20 Correct 473 ms 324 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 478 ms 328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 476 ms 412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 280 KB Output is correct
2 Correct 495 ms 292 KB Output is correct
3 Correct 487 ms 284 KB Output is correct
4 Correct 480 ms 288 KB Output is correct
5 Correct 481 ms 284 KB Output is correct
6 Correct 479 ms 292 KB Output is correct
7 Correct 475 ms 300 KB Output is correct
8 Correct 470 ms 288 KB Output is correct
9 Correct 477 ms 300 KB Output is correct
10 Correct 482 ms 288 KB Output is correct
11 Correct 490 ms 280 KB Output is correct
12 Correct 481 ms 288 KB Output is correct
13 Correct 476 ms 312 KB Output is correct
14 Correct 486 ms 292 KB Output is correct
15 Correct 475 ms 308 KB Output is correct
16 Correct 475 ms 280 KB Output is correct
17 Correct 471 ms 288 KB Output is correct
18 Correct 474 ms 308 KB Output is correct
19 Correct 477 ms 288 KB Output is correct
20 Correct 473 ms 324 KB Output is correct
21 Runtime error 478 ms 328 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -