This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int long long
using namespace std;
const ll MOD = 1e9 + 7;
ll powerm(ll a,ll b,ll m) { //m-> mod
if(b==0) {
return 1;
}
ll res=powerm(a,b/2,m);
if(b%2) {
return ((res*res)%m*(a%m))%m;
}
return (res*res)%m;
}
//INVERSE -> a^(m-2) ...m -> prime
ll power(ll a,ll b) {
if(b==0) {
return 1;
}
ll res=power(a,b/2);
if(b%2==0) {
return res*res;
}
return res*res*a;
}
/*void facm(ll m) { //factorial mod precompute
fac[0]=1;
for(int i=1;i<fac.size();i++) { //name an array fac
fac[i]=((i)%m*fac[i-1])%m;
}
return;
}
ll choose(ll a,ll b,ll m) { //a choose b mod m
ll ans=((fac[a]*(powerm(fac[a-b],m-2,m)))%m*powerm(fac[b],m-2,m))%m;
return ans;
}*/
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("revegetate.in","r",stdin);
//freopen("revegetate.out","w",stdout);
int n,d;
cin>>n>>d;
vector<int>vec(n+1),t(n+1);
vec[0]=0,t[0]=0,t[1]=1;
for(int i=1;i<=n;i++) {
cin>>vec[i];
}
sort(vec.begin(),vec.end());
for(int i=2;i<=n;i++) {
int first=1,last=i,j;
while(first<=last) {
int mid=(first+last)/2;
if(vec[mid]>=vec[i]-d) {
j=mid;
last=mid-1;
} else {
first=mid+1;
}
}
t[i]=(t[i-1]*(i-j+1))%MOD;
}
cout<<t[n];
return 0;
}
Compilation message (stderr)
tower.cpp: In function 'int main()':
tower.cpp:71:24: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | t[i]=(t[i-1]*(i-j+1))%MOD;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |