oj.uz

Submission #237607

# Submission time Handle Problem Language Result Execution time Memory
237607 2020-06-07T17:42:16 Z Pbezz Rack (eJOI19_rack) C++14
100 / 100
 203 ms 30840 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define MAXN 100005
typedef pair<int, int> pii;

ll fast(ll base, ll exp){

	if(exp==0) return 1%MOD;

	ll u = fast(base,exp/2); 

	u=(u*u)%MOD;

	if (exp%2==1) u=(u*base)%MOD;

	return u; 
}


ll solve(ll n, ll k){

	if(n==1&&k==1)return 1%MOD;
	if(n==1&&k==2)return 2%MOD;

	ll ans = fast(2,n-1);

	if(k%2==0)return (solve(n-1,k/2)+ans)%MOD;
	else return solve(n-1,(k+1)/2)%MOD;


}


int main(){

	ll n,k,ans;
	cin>>n>>k; 

	ans=solve(n,k)%MOD;

	if(ans<0)ans+=MOD;

	cout<<ans<<'\n';

return 0; 
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 256 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 14 ms 2048 KB Output is correct
15 Correct 203 ms 30840 KB Output is correct