Task: | Ruudukko |
Sender: | andreibe |
Submission time: | 2022-10-31 12:02:50 +0200 |
Language: | Java |
Status: | READY |
Result: | 61 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | ACCEPTED | 33 |
#3 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.07 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.07 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.07 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.12 s | 2, 3 | details |
#5 | ACCEPTED | 0.13 s | 2, 3 | details |
#6 | ACCEPTED | 0.14 s | 2, 3 | details |
#7 | ACCEPTED | 0.64 s | 3 | details |
#8 | ACCEPTED | 0.94 s | 3 | details |
#9 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
//package com.patonki;import java.io.*;import java.util.*;class Pair implements Comparable<Pair>{int value;int y;int x;public Pair(int value, int y, int x) {this.value = value;this.y = y;this.x = x;}@Overridepublic int compareTo(Pair o) {int val = Integer.compare(value,o.value);if (val != 0) return val;int y = Integer.compare(this.y,o.y);if (y != 0) return y;return Integer.compare(x,o.x);}@Overridepublic String toString() {return "Pair{" +"value=" + value +", y=" + y +", x=" + x +'}';}}public class Lol {static long[][] d = new long[1010][1010];static int M = 1000000007;static long[] rivit = new long[1010];static long[] kolumnit = new long[1010];public static void main(String[] args) throws IOException {//createTestData();//System.exit(0);BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));//BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("lol.txt")));int n = Integer.parseInt(reader.readLine());long time = System.currentTimeMillis();ArrayList<Pair> pairs = new ArrayList<>();for (int y = 0; y < n; y++) {String[] rivi = reader.readLine().split(" ");for (int x = 0; x < rivi.length; x++) {int val = Integer.parseInt(rivi[x]);pairs.add(new Pair(val,y,x));}}Collections.sort(pairs);int curnumber = pairs.get(0).value;ArrayList<Pair> toedit = new ArrayList<>();//System.out.println(pairs);for (Pair pair : pairs) {int y = pair.y;int x = pair.x;int value = pair.value;if (value != curnumber) {for (Pair p : toedit) {rivit[p.y] += d[p.y][p.x];rivit[p.y] %= M;kolumnit[p.x] += d[p.y][p.x];kolumnit[p.x] %= M;}toedit.clear();curnumber = value;}d[y][x] += rivit[y] + kolumnit[x] + 1;d[y][x] %= M;//System.out.println(rivit[y] + " " + kolumnit[x] + " " + d[y][x]);toedit.add(pair);}long sum = 0;StringBuilder builder = new StringBuilder();for (int y = 0; y < n; y++) {for (int x = 0; x < n; x++) {sum += d[y][x];//System.out.println(d[y][x]);//builder.append(d[y][x]).append(" ");sum %= M;}//builder.append("\n");}System.out.println(sum);//System.out.println(System.currentTimeMillis()-time);//System.out.println(builder);}private static void createTestData() throws IOException {FileWriter writer = new FileWriter("lol.txt");Random random = new Random();int n = 1000;StringBuilder builder = new StringBuilder();for (int y = 0; y < n; y++) {for (int x = 0; x < n; x++) {builder.append(random.nextInt(999)+1).append(" ");}builder.append("\n");}writer.write(builder.substring(0,builder.length()-1));writer.close();}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 1 1 1 1 1 1 1 1 1 |
correct output |
---|
9 |
user output |
---|
9 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 1 2 3 6 5 4 7 8 9 |
correct output |
---|
135 |
user output |
---|
135 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 7 8 1 4 5 4 3 9 6 |
correct output |
---|
57 |
user output |
---|
57 |
Test 4
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
10000 |
user output |
---|
10000 |
Test 5
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
187458477 |
user output |
---|
187458477 |
Test 6
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 2995 8734 1018 2513 7971 5063 ... |
correct output |
---|
964692694 |
user output |
---|
964692694 |
Test 7
Group: 3
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1000000 |
user output |
---|
1000000 |
Test 8
Group: 3
Verdict: ACCEPTED
input |
---|
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
229147081 |
user output |
---|
229147081 |
Test 9
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 520283 805991 492643 75254 527... |
correct output |
---|
951147313 |
user output |
---|
(empty) |