Submission #1131298
Source Code Expand
#include <functional>
#include <list>
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <deque>
#include <stack>
#include <cassert>
using namespace std;
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define ALL(x) (x).begin(),(x).end()
#define CASET2 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d:\n", case_n++) : 0), ___T-- > 0)
#define CASET1 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d: ", case_n++) : 0), ___T-- > 0)
#define CASET int ___T; scanf("%d ", &___T); while (___T-- > 0)
#define SZ(X) ((int)(X).size())
#define LEN(X) strlen(X)
#define REP(i,n) for(int i=0;i<int(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=int(b);i++)
#define PER1(i,a,b) for(int i=(a);i>=(b);i--)
#define REPL(i,x) for(int i=0;x[i];i++)
#define PER(i,n) for(int i=(n)-1;i>=0;i--)
#define RI1(x) scanf("%d",&x)
#define RI2(x,y) RI1(x), RI1(y)
#define RI3(x,y...) RI1(x), RI2(y)
#define RI4(x,y...) RI1(x), RI3(y)
#define RI5(x,y...) RI1(x), RI4(y)
#define RI6(x,y...) RI1(x), RI5(y)
#define GET_MACRO(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define RI(argv...) GET_MACRO(argv, RI6, RI5, RI4, RI3, RI2, RI1)(argv)
#define DRI(argv...) int argv;RI(argv)
#define WRI(argv...) while (RI(argv) != EOF)
#define DWRI(x...) int x; WRI(x)
#define RS(x) scanf("%s",x)
#define MP make_pair
#define PB push_back
#define MS0(x) memset(x,0,sizeof(x))
#define MS1(x) memset(x,-1,sizeof(x))
#define X first
#define Y second
#define V(x) vector<x >
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;
const int INF = 1000000000;
void print(int i) { printf("%d", i); }
void print(LL i);
template<class T> void PI(T i) { print(i); puts(""); }
template<class T> void PIS(T i) { print(i); printf(" "); }
template<class T>
void PV(T const &v, int N) {
REP(i, N) {
print(v[i]);
printf("%c", i == N-1 ? '\n' : ' ');
}
}
template<class T> void PV(T const &v) { PV(v, SZ(v)); }
template<class T, class S> bool has_bit(T mask, S i) { return (mask >> i) & 1; }
long long shift(int i) { return 1ll << i; }
template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
int popcount(int x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
#include <unordered_set>
#include <unordered_map>
#define EB emplace_back
#define RL(x) scanf("%lld", &(x))
#define PL(x) printf("%lld\n", x)
#define DRL(x) LL x; RL(x)
#define PZ(x) PI((x).i);
template<class Short, class Long>
struct ZZ {
static Short MOD;
Short i;
ZZ():i(0) {}
ZZ(Short _i): i(_i >= 0 ? _i : _i + MOD) {}
ZZ(Long _i): i(_i % MOD) {}
void operator +=(const ZZ& z) { i += z.i; if(i >= MOD) i -= MOD; }
void operator -=(const ZZ& z) { i -= z.i; if(i < 0) i += MOD; }
void operator *=(const ZZ& z) { i = (Long) i * z.i % MOD; }
void operator /=(const ZZ& z) { (*this) *= z.inverse(); }
ZZ operator +(const ZZ& z) const { ZZ ret(i); ret += z; return ret; }
ZZ operator -(const ZZ& z) const { ZZ ret(i); ret -= z; return ret; }
ZZ operator *(const ZZ& z) const { ZZ ret(i); ret *= z; return ret; }
ZZ operator /(const ZZ& z) const { return (*this) * z.inverse(); }
// ZZ operator -() const { return ZZ(-i); }
ZZ inverse() const {
return pow(MOD - 2);
}
ZZ pow(long long b) const {
ZZ x=Short(1),y=*this;
while(b > 0){
if(b%2 == 1)
x *= y;
y *= y; // squaring the base
b /= 2;
}
return x;
}
static vector<ZZ> factorial, inv_factorial;
static ZZ fact(int n) {
while(factorial.size() <= n)
factorial.push_back(factorial.back() * SZ(factorial));
return factorial.at(n);
}
static ZZ inv_fact(int n) {
if (n < inv_factorial.size())
return inv_factorial.at(n);
int old_size = inv_factorial.size();
inv_factorial.resize(n+1);
inv_factorial.at(n) = fact(n).inverse();
for (int i = n-1; i >= old_size; i--) {
inv_factorial[i] = inv_factorial.at(i+1) * (i+1);
}
return inv_factorial.at(n);
}
static ZZ choose0(int n, int k) {
assert(n < 1e7);
if(n < k) return 0;
return fact(n) * (inv_fact(k) * inv_fact(n-k));
}
static ZZ choose1(int n, int k) {
assert(k < 1e7);
if (n < k) return 0;
if (k == 0) return 1;
return choose1(n-1, k-1) * n / k;
}
static pair<ZZ,int> factModExp(int n) {
if (n == 0) return MP(1, 0);
int e = n / MOD;
pair<ZZ,int> pr = factModExp(e);
if (e % 2) {
return MP(ZZ(0) - pr.first * fact(n % MOD), pr.second + e);
} else {
return MP(pr.first * fact(n % MOD), pr.second + e);
}
}
static ZZ choose2(int n, int k) {
assert(MOD < 1e7);
pair<ZZ,int> p1 = factModExp(n), p2 = factModExp(k), p3 = factModExp(n-k);
if (p1.second > p2.second + p3.second) return 0;
assert(p1.second == p2.second + p3.second);
return p1.first / (p2.first * p3.first);
}
};
typedef ZZ<int, long long> Z;
template<> int Z::MOD = 1000000007;
template<> vector<Z> Z::factorial(1, 1);
template<> vector<Z> Z::inv_factorial(1, 1);
long long mul(long long a,long long b,long long mod=Z::MOD){
long long x = 0,y=a%mod;
while(b > 0){
if(b%2 == 1){
x = x+y;
if(x >= mod) x -= mod;
}
y = y*2;
if(y >= mod) y -= mod;
b /= 2;
}
return x%mod;
}
long long pow(long long a, long long b, long long c=Z::MOD){
long long x=1,y=a; // ll is taken to avoid overflow of intermediate results
while(b > 0){
if(b%2 == 1){
x=mul(x, y, c);
}
y = mul(y, y, c); // squaring the base
b /= 2;
}
return x%c;
}
int main() {
DRI(N);
VI x(N);
REP(i, N) {
RI(x[i]);
}
Z ans = 1;
int j = 0, c = 0;
while (c < N) {
while (j < N && x[j] >= 2 * (j-c) + 1) {
j++;
}
ans *= min(N, j+1) - c;
c++;
}
PZ(ans);
return 0;
}
Submission Info
Submission Time
2017-02-25 21:19:36+0900
Task
A - Robot Racing
User
johnathan79717
Language
C++14 (GCC 5.4.1)
Score
900
Code Size
6578 Byte
Status
AC
Exec Time
14 ms
Memory
640 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:203:9: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
DRI(N);
^
./Main.cpp:206:13: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
RI(x[i]);
^
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
1 ms
256 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
12 ms
640 KB
2_01.txt
AC
12 ms
640 KB
2_02.txt
AC
14 ms
640 KB
2_03.txt
AC
12 ms
640 KB
2_04.txt
AC
12 ms
640 KB
2_05.txt
AC
12 ms
640 KB
2_06.txt
AC
12 ms
640 KB
2_07.txt
AC
12 ms
640 KB
2_08.txt
AC
12 ms
640 KB
2_09.txt
AC
12 ms
640 KB
2_10.txt
AC
12 ms
640 KB
2_11.txt
AC
14 ms
640 KB
2_12.txt
AC
14 ms
640 KB