| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 263623 |
2020-08-13T22:44:33 Z |
ijxjdjd |
Boat (APIO16_boat) |
Java 11 |
|
79 ms |
12292 KB |
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
public class boat {
static long[][] choose = new long[501][501];
static long[] inverse = new long[505];
public static long inverse(long a, long mod) {
long[] inv = extended_gcd(a, mod);
if (inv[0] != 1) {
return 0;
}
else {
return (inv[1] + 2*mod)%mod;
}
}
public static long[] extended_gcd(long a, long b) {
//three numbers, first is gcd, second is x, third is y
if (a == 0) {
return new long[]{b, 0, 1};
}
long[] next = extended_gcd(b%a, a);
long tempX = next[1];
next[1] = next[2] - (b/a) * next[1];
next[2] = tempX;
return next;
}
@SuppressWarnings("unchecked")
public static void main(String[] args) {
// InputReader in = new InputReader(System.in);
// PrintWriter out = new PrintWriter(System.out);
// int N = in.nextInt();
// int[][] intervals = new int[N][2];
// HashSet<Integer> points = new HashSet<>();
// for (int i = 0; i <= 500; i++) {
// choose[i][0] = 1;
// for (int j = 1; j <= i; j++) {
// choose[i][j] = (choose[i-1][j] + choose[i-1][j-1])%MOD;
// }
// }
// for (int i = 1; i < inverse.length; i++) {
// inverse[i] = inverse(i, MOD);
// }
// for (int i = 0; i < N; i++) {
// intervals[i][0] = in.nextInt();
// intervals[i][1] = in.nextInt();
// points.add(intervals[i][0]);
// points.add(intervals[i][1]+1);
// }
// ArrayList<Integer> pSort = new ArrayList<>(points);
// ArrayList<Integer>[] items = new ArrayList[pSort.size()];
// for (int i = 0; i < pSort.size(); i++) {
// items[i] = new ArrayList<Integer>();
// }
// Collections.sort(pSort);
// for (int i = 0; i < N; i++) {
// boolean flag = false;
// for (int j = 0; j < pSort.size(); j++) {
// if (pSort.get(j) == intervals[i][1]+1) {
// break;
// }
// if (flag || pSort.get(j) == intervals[i][0]) {
// flag = true;
// items[j].add(i+1);
// }
//
// }
// }
// long[] dp = new long[N+1];
// dp[0] = 1;
// for (int i = 0; i < pSort.size()-1; i++) {
// long[] pref = new long[N+1];
// pref[0] = dp[0];
// for (int j = 1; j <= N; j++) {
// pref[j] = dp[j] + pref[j-1];
// }
// long[] pathCount = new long[items[i].size()];
// long sz = pSort.get(i+1) - pSort.get(i);
// long[] szCount = new long[items[i].size()];
// szCount[0] = (sz*(sz-1))/2;
// for (int j = 1; j < items[i].size(); j++) {
// szCount[j] = szCount[j-1]*(sz - j - 1)*inverse[j+2];
// }
// for (int j = 1; j < items[i].size(); j++) {
// for (int k = 0; k < j; k++) {
// pathCount[j] += szCount[k] * choose[j-1][k];
// }
// }
// pathCount[0] = sz;
// for (int j = 0; j < items[i].size(); j++) {
// for (int d = 0; d <= j; d++) {
// dp[items[i].get(j)] += pathCount[d]*pref[items[i].get(j-d)-1];
// }
// }
// }
// long tot = 0;
// for (int i = 1; i < dp.length; i++) {
// tot += dp[i];
// }
// out.println(tot);
// out.close();
}
static long MOD = (int)(1e9) + 7;
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
try {
return reader.readLine();
}
catch (IOException e) {
throw new RuntimeException(e);
}
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
12292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
