Submission #172432


Source Code Expand

Copy
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
 
public class Main {
//    private static final String INPUT_PATH = "C:\\atcoder\\b_008_004.txt";
    private static final String INPUT_PATH = null;

    int D = 1000000007;
    public void solve() { 
        try {
            br = new BufferedReader(new InputStreamReader(
                    INPUT_PATH == null ? System.in : new FileInputStream(new File(INPUT_PATH))));

            int N = readInt();
            int[] tA = readIntArray();

            
            int before = tA[0];
            
            int cnt = 0;
            long max = 1;
            for (int i = 1 ; i < N; i++) {
                cnt ++;

                if (tA[i] != -1) {
                    int next = tA[i] - before;
                    long patern = 1;
                    long x = next + cnt;
                    for (int j = 1; j < cnt; j++) {
                        patern = patern * (x - j ) / (j) % D;
                    }
                    max = (max * patern) % D;
                    
                    before = tA[i];
                    cnt = 0;
                }
            }
            
            pw.println(max);
            
            
        } catch(Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception igunore) {}
        }
    }

    boolean deepEquals(int[] i1, int[] i2) {
        if (i1.length != i2.length) return false;
        for (int i = 0 ; i < i1.length; i++) if (i1[i] != i2[i]) return false;
        return true;
    }
    String getKey(int[] i) {
        StringBuilder sb = new StringBuilder();
        for (int s : i) sb.append(" " + s);
        return sb.toString();
    }

    private int brPos = 0;
    private int[] brBuf = null;
    
    private int readBufInt() throws IOException {
        if (brBuf == null || brBuf.length == brPos) {
            brBuf = readIntArray();
            brPos = 0;
        }
        return brBuf[brPos++];
    }

    private int readInt() throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private long readLong() throws IOException {
        return Long.parseLong(br.readLine());
    }

    private int[] readIntArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        int[] out = new int[cnt];
        for (int i = 0; i < cnt; i++) out[i] = Integer.parseInt(s[i]);
        return out;
    }

    private Integer[] convIntArray(int[] arg) {
        int len = arg.length;
        Integer[] res = new Integer[len];
        for (int i = 0; i < len; i++) res[i] = arg[i];
        return res;
    }
    
    private long[] readLongArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        long[] out = new long[cnt];
        for (int i = 0; i < cnt; i++) out[i] = Long.parseLong(s[i]);
        return out;
    }

    private String[] readStrArray() throws IOException {
        String[] s = br.readLine().split(" ");
        return s;
    }

    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
     }
    
    void permutationRange(int from, int to) {
        int cnt = to - from + 1;
        int[] elements = new int[cnt];
        for (int i = 0 ; i <  cnt; i++) elements[i] = from++;
        permutation(elements, 0, cnt - 1);
    }

    void permutationString(String element) {
        char[] elements = element.toCharArray();
        permutationString(elements, 0, elements.length - 1);
    }

    
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 

            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            int tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutation(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    void permutationString(char[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 
            
            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            char tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutationString(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    private static long gcd(long n1, long n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }
    private static int gcd(int n1, int n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }

    public static void main(String[] args) {
        long from = System.currentTimeMillis();
        Main app = new Main();
        app.solve();
        pw.flush();
        pw.println(System.currentTimeMillis() - from);
    }

    void printMatrix(int[][] p) {
        for (int[] i : p) printArray(i);
    }
    
    void printArray(int[] p) {
        for (int i : p) System.out.print(i + " ");
        System.out.println();
    }

   void debug(Object ... o) {
       pw.write(deepToString(o));
   }
   BufferedReader br = null;
   static PrintWriter pw = new PrintWriter(System.out);

   class Type {
       int x, y;
       Type (int x, int y) {
           this.x = x;
           this.y = y;
       }
   }
}

Submission Info

Submission Time
Task C - タコヤ木
User tochukaso
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 5882 Byte
Status WA
Exec Time 470 ms
Memory 24520 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 50 0 / 30 0 / 20
Status
AC × 3
AC × 13
WA × 1
AC × 22
WA × 4
AC × 24
WA × 12
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 384 ms 20824 KB
sample_02.txt AC 388 ms 20704 KB
sample_03.txt AC 386 ms 20696 KB
subtask1_01.txt AC 386 ms 20676 KB
subtask1_02.txt AC 385 ms 20824 KB
subtask1_03.txt AC 434 ms 20700 KB
subtask1_04.txt AC 396 ms 20700 KB
subtask1_05.txt AC 420 ms 20828 KB
subtask1_06.txt AC 421 ms 20708 KB
subtask1_07.txt WA 395 ms 20708 KB
subtask1_08.txt AC 392 ms 20700 KB
subtask1_09.txt AC 400 ms 20712 KB
subtask1_10.txt AC 403 ms 20696 KB
subtask1_11.txt AC 400 ms 20712 KB
subtask1_12.txt AC 426 ms 20696 KB
subtask2_01.txt AC 392 ms 20700 KB
subtask2_02.txt AC 400 ms 20696 KB
subtask2_03.txt AC 398 ms 20704 KB
subtask2_04.txt AC 401 ms 20832 KB
subtask2_05.txt AC 414 ms 20836 KB
subtask2_06.txt AC 413 ms 20828 KB
subtask2_07.txt WA 408 ms 20956 KB
subtask2_08.txt AC 417 ms 21728 KB
subtask2_09.txt WA 414 ms 20952 KB
subtask2_10.txt WA 408 ms 20952 KB
subtask2_11.txt AC 423 ms 21720 KB
subtask2_12.txt AC 424 ms 21600 KB
subtask3_01.txt AC 405 ms 20700 KB
subtask3_02.txt AC 401 ms 20700 KB
subtask3_03.txt AC 414 ms 20824 KB
subtask3_04.txt WA 436 ms 22100 KB
subtask3_05.txt WA 399 ms 20696 KB
subtask3_06.txt WA 425 ms 21596 KB
subtask3_07.txt WA 430 ms 20960 KB
subtask3_08.txt AC 464 ms 24520 KB
subtask3_09.txt WA 447 ms 21460 KB
subtask3_10.txt WA 470 ms 24464 KB
subtask3_11.txt WA 434 ms 21596 KB
subtask3_12.txt WA 464 ms 24460 KB