Contest Duration: - (local time) (90 minutes) Back to Home

Submission #171543

Source Code Expand

Copy
```import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
int n = ni();
int[] a = na(n);
int mod = 1000000007;
long ret = 1;
for(int i = 0;i < n;){
if(i == n-1)break;
if(a[i] != -1){
int j;
for(j = i+1;j < n && a[j] == -1;j++);
long num = 1, den = 1;
for(int k = 1;k <= j-i-1;k++){
num = num * (a[j]-a[i]+j-i-1-k+1) % mod;
den = den * k % mod;
}
ret = ret * num % mod * invl(den, mod) % mod;
i = j;
}
}
out.println(ret);
}

public static long invl(long a, long mod)
{
long b = mod;
long p = 1, q = 0;
while(b > 0){
long c = a / b;
long d;
d = a; a = b; b = d % b;
d = p; p = q; q = d - c * q;
}
return p < 0 ? p + mod : p;
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;

try {
is.mark(1000);
while(true){
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
```

#### Submission Info

Submission Time 2014-05-17 21:11:53+0900 C - タコヤ木 uwi Java (OpenJDK 1.7.0) 100 4108 Byte AC 446 ms 20592 KB

#### Judge Result

Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
 AC × 3
 AC × 14
 AC × 26
 AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 415 ms 20156 KB
sample_02.txt AC 398 ms 20144 KB
sample_03.txt AC 393 ms 20152 KB
subtask1_01.txt AC 386 ms 20152 KB
subtask1_02.txt AC 397 ms 20148 KB
subtask1_03.txt AC 400 ms 20136 KB
subtask1_04.txt AC 409 ms 20108 KB
subtask1_05.txt AC 438 ms 20196 KB
subtask1_06.txt AC 406 ms 20152 KB
subtask1_07.txt AC 410 ms 20156 KB
subtask1_08.txt AC 416 ms 20156 KB
subtask1_09.txt AC 407 ms 20156 KB
subtask1_10.txt AC 423 ms 20120 KB
subtask1_11.txt AC 400 ms 20156 KB
subtask1_12.txt AC 397 ms 20108 KB
subtask2_01.txt AC 391 ms 20148 KB
subtask2_02.txt AC 408 ms 20220 KB
subtask2_03.txt AC 422 ms 20192 KB
subtask2_04.txt AC 416 ms 20132 KB
subtask2_05.txt AC 418 ms 20128 KB
subtask2_06.txt AC 416 ms 20116 KB
subtask2_07.txt AC 412 ms 20152 KB
subtask2_08.txt AC 405 ms 20152 KB
subtask2_09.txt AC 416 ms 20152 KB
subtask2_10.txt AC 424 ms 20132 KB
subtask2_11.txt AC 423 ms 20136 KB
subtask2_12.txt AC 417 ms 20152 KB
subtask3_01.txt AC 440 ms 20124 KB
subtask3_02.txt AC 409 ms 20152 KB
subtask3_03.txt AC 408 ms 20188 KB
subtask3_04.txt AC 426 ms 20444 KB
subtask3_05.txt AC 400 ms 20188 KB
subtask3_06.txt AC 402 ms 20152 KB
subtask3_07.txt AC 431 ms 20112 KB
subtask3_08.txt AC 422 ms 20592 KB
subtask3_09.txt AC 422 ms 20156 KB
subtask3_10.txt AC 440 ms 20464 KB
subtask3_11.txt AC 427 ms 20232 KB
subtask3_12.txt AC 446 ms 20576 KB