Submission #1131179
Source Code Expand
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author RiaD
*/
#include <iostream>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <stdexcept>
#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
if(!(condition)) { \
throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif
/**
* Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
* it's reference type is not a reference.
*
* It doesn't return reference because
* 1. Anyway it'll not satisfy requirement [forward.iterators]/6
* If a and b are both dereferenceable, then a == b if and only if *a and
* b are bound to the same object.
* 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
*
* Note, reverse_iterator is not guaranteed to work now too since it works only with bidirectional iterators,
* but it's seems to work at least on my implementation.
*
* It's not really useful anywhere except iterating anyway.
*/
template <typename T>
class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
public:
explicit IntegerIterator(T value): value(value) {
}
IntegerIterator& operator++() {
++value;
return *this;
}
IntegerIterator operator++(int) {
IntegerIterator copy = *this;
++value;
return copy;
}
IntegerIterator& operator--() {
--value;
return *this;
}
IntegerIterator operator--(int) {
IntegerIterator copy = *this;
--value;
return copy;
}
T operator*() const {
return value;
}
bool operator==(IntegerIterator rhs) const {
return value == rhs.value;
}
bool operator!=(IntegerIterator rhs) const {
return !(*this == rhs);
}
private:
T value;
};
template <typename T>
class IntegerRange {
public:
IntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin <= end);
}
IntegerIterator<T> begin() const {
return IntegerIterator<T>(begin_);
}
IntegerIterator<T> end() const {
return IntegerIterator<T>(end_);
}
private:
T begin_;
T end_;
};
template <typename T>
class ReversedIntegerRange {
typedef std::reverse_iterator<IntegerIterator<T>> IteratorType;
public:
ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin >= end);
}
IteratorType begin() const {
return IteratorType(IntegerIterator<T>(begin_));
}
IteratorType end() const {
return IteratorType(IntegerIterator<T>(end_));
}
private:
T begin_;
T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
return ReversedIntegerRange<T>(from + 1, to);
}
#include <assert.h>
#include <type_traits>
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
static T identity() {
return 1;
}
};
template <typename T>
T identity() {
return IdentityHelper<T>::identity();
}
/**
* ax + by = result
*/
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
T d = extendedGcd(b % a, a, y, x);
x -= (b / a) * y;
return d;
}
template <typename T>
class Zn {
public:
Zn(): value(0) {
}
/**
* Instead of ctor, to allow not to normalize in ctor
*/
static Zn valueOf(int value) {
int x = value % mod();
if (x < 0) {
x += mod();
}
return Zn(x);
}
static Zn valueOf(long long value) {
int x = static_cast<int>(value % mod());
if (x < 0) {
x += mod();
}
return Zn(x);
}
static Zn rawValueOf(int value) {
SPCPPL_ASSERT(value >= 0 && value < mod());
return Zn(value);
}
Zn& operator=(int rhs) {
return *this = Zn::valueOf(rhs);
}
Zn& operator=(long long rhs) {
return *this = Zn::valueOf(rhs);
}
Zn& operator+=(const Zn& rhs) {
value += rhs.value;
if (value >= mod()) {
value -= mod();
}
return *this;
}
Zn& operator+=(int rhs) {
return *this += Zn::valueOf(rhs);
}
Zn& operator+=(long long rhs) {
return *this += Zn::valueOf(rhs);
}
Zn& operator-=(const Zn& rhs) {
value -= rhs.value;
if (value < 0) {
value += mod();
}
return *this;
}
Zn& operator-=(int rhs) {
return *this -= Zn::valueOf(rhs);
}
Zn& operator-=(long long rhs) {
return *this -= Zn::valueOf(rhs);
}
Zn& operator*=(const Zn& rhs) {
long long result = static_cast<long long>(value) * static_cast<long long>(rhs.value);
value = static_cast<int>(result % mod());
return *this;
}
Zn& operator*=(int rhs) {
return *this *= Zn::valueOf(rhs);
}
Zn& operator*=(long long rhs) {
return *this *= Zn::valueOf(rhs);
}
Zn operator-() const {
if (value == 0) {
return *this;
}
else {
return Zn(mod() - value);
}
}
Zn& operator/=(const Zn& rhs) {
return *this *= rhs.inversed();
}
Zn& operator/=(int rhs) {
return *this /= Zn::valueOf(rhs);
}
Zn& operator/=(long long rhs) {
return *this /= Zn::valueOf(rhs);
}
bool operator==(const Zn& rhs) const {
return value == rhs.value;
}
Zn inversed() const {
SPCPPL_ASSERT(value != 0);
int x, y;
int gcd = extendedGcd(value, mod(), x, y);
(void) gcd;
SPCPPL_ASSERT(gcd == 1);
if (x < 0) {
x += mod();
}
return Zn(x);
}
template <typename U>
friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
template <typename U>
friend std::istream& operator>>(std::istream&, Zn<U>& zn);
int intValue() const {
return value;
}
private:
/**
* No normalization performed
*/
explicit Zn(int value): value(value) {
}
int value;
constexpr static int mod() {
return T::value;
}
template <int N = T::value>
static constexpr bool positive_or_runtime(int) {
return N > 0;
}
static constexpr bool positive_or_runtime(...) {
return true;
}
static_assert(
std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
"T::value must be int"
);
static_assert(positive_or_runtime(0), "Mod has to be positive integer");
};
template <typename T>
bool operator==(const Zn<T>& lhs, int rhs) {
return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(int lhs, const Zn<T>& rhs) {
return rhs == lhs;
}
template <typename T>
bool operator==(const Zn<T>& lhs, long long rhs) {
return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(long long lhs, Zn<T>& rhs) {
return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, int rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(int lhs, const Zn<T>& rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, long long rhs) {
return !(lhs == rhs);
}
template <typename T>
bool operator!=(long long rhs, const Zn<T>& lhs) {
return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(int lhs, const Zn<T>& rhs) {
return rhs + lhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy += rhs;
}
template <typename T>
Zn<T> operator+(long long lhs, const Zn<T>& rhs) {
return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(int lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy -= rhs;
}
template <typename T>
Zn<T> operator-(long lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(int lhs, const Zn<T>& rhs) {
return rhs * lhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy *= rhs;
}
template <typename T>
Zn<T> operator*(long long lhs, const Zn<T>& rhs) {
return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, int rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(int lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, long long rhs) {
Zn<T> copy = lhs;
return copy /= rhs;
}
template <typename T>
Zn<T> operator/(long long lhs, const Zn<T>& rhs) {
return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
long long value;
stream >> value;
zn.value = static_cast<int>(value % T::value);
return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
static Zn<T> identity() {
return Zn<T>::valueOf(1);
}
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
using namespace std;
class TaskA {
public:
void solve(std::istream& in, std::ostream& out) {
int n;
in >> n;
int cnt = 0;
using Z = ZnConst<1000000007>;
Z ans = Z::valueOf(1);
for (int i: range(n)) {
int x;
in >> x;
++cnt;
if (x < 2 * cnt - 1) {
ans *= cnt;
--cnt;
}
}
for (int i: inclusiveRange(1, cnt)) {
ans *= i;
}
out << ans << "\n";
}
};
int main() {
std::ios_base::sync_with_stdio(false);
TaskA solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
in.tie(nullptr);
out << std::fixed;
out.precision(20);
solver.solve(in, out);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Robot Racing |
User |
riadwaw |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
11689 Byte |
Status |
AC |
Exec Time |
11 ms |
Memory |
896 KB |
Judge Result
Set Name |
Sample |
Subtask |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
400 / 400 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
6 ms |
896 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
1 ms |
256 KB |
1_03.txt |
AC |
1 ms |
256 KB |
1_04.txt |
AC |
1 ms |
256 KB |
1_05.txt |
AC |
1 ms |
256 KB |
1_06.txt |
AC |
1 ms |
256 KB |
1_07.txt |
AC |
1 ms |
256 KB |
1_08.txt |
AC |
1 ms |
256 KB |
1_09.txt |
AC |
1 ms |
256 KB |
1_10.txt |
AC |
1 ms |
256 KB |
2_00.txt |
AC |
9 ms |
256 KB |
2_01.txt |
AC |
9 ms |
256 KB |
2_02.txt |
AC |
11 ms |
256 KB |
2_03.txt |
AC |
9 ms |
256 KB |
2_04.txt |
AC |
9 ms |
256 KB |
2_05.txt |
AC |
9 ms |
256 KB |
2_06.txt |
AC |
9 ms |
256 KB |
2_07.txt |
AC |
9 ms |
256 KB |
2_08.txt |
AC |
9 ms |
256 KB |
2_09.txt |
AC |
9 ms |
256 KB |
2_10.txt |
AC |
9 ms |
256 KB |
2_11.txt |
AC |
11 ms |
256 KB |
2_12.txt |
AC |
11 ms |
256 KB |