CSES - Datatähti 2023 alku - Results
Submission details
Task:Ruudukko
Sender:lompakkomies
Submission time:2022-11-02 19:27:23 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.13 s1, 2, 3details
#2ACCEPTED0.13 s1, 2, 3details
#3ACCEPTED0.13 s1, 2, 3details
#40.27 s2, 3details
#5ACCEPTED0.61 s2, 3details
#60.60 s2, 3details
#7--3details
#8--3details
#9--3details

Code

import java.util.Scanner;
import java.math.BigInteger;
public class Ruudukko {
static int n = 0;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
int[][] arr = new int[n][n];
int[][] arr2 = new int[n][n];
int[] arr3 = new int[n*n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
arr[i][j] = scan.nextInt();
arr2[i][j] = 1;
}
}
int m = -1;
int i2 = 0;
int m2 = 0;
for(int i = 0; i < n*n; i++) {
arr3[i] = n*n+1;
}
while(i2 < n*n) {
if(i2%n == 0) {
m++;
}
if(checkArr(arr3, arr[m][i2%n])) {
arr3[m2] = arr[m][i2%n];
m2++;
}
i2++;
}
int[] arr4 = new int[m2];
for(int i = 0; i < arr4.length; i++) {
arr4[i] = arr3[i];
}
quickSort(arr4, 0, arr4.length-1);
System.out.print("\n");
m2 = 0;
for(int i = 1; i <= n*n; i++) {
if(arr4[m2] == i) {
m2++;
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
if(arr[j][k] == i) {
for(int l = 0; l < n; l++) {
if(arr[j][l] < i) {
arr2[j][k] = (arr2[j][k] + arr2[j][l])%1000000007;
}
}
for(int l = 0; l < n; l++) {
if(arr[l][k] < i) {
arr2[j][k] = (arr2[j][k] + arr2[l][k])%1000000007;
}
}
}
}
}
}
}
int sum = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
sum = (sum + arr2[i][j])%1000000007;
}
}
System.out.print(sum);
}
public static boolean checkArr(int[] arr3, int key) {
for(int i = 0; i < n*n; i++) {
if(arr3[i] == key) {
return false;
}
}
return true;
}
// quicksort algorithm from https://www.geeksforgeeks.org/quick-sort/
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(int[] arr, int low, int high)
{
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
3
1 1 1
1 1 1
1 1 1

correct output
9

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds...

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:

input
100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
10000

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds...

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:

input
100
2995 8734 1018 2513 7971 5063 ...

correct output
964692694

user output
(empty)

Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6268 out of bou...

Test 7

Group: 3

Verdict:

input
1000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
1000000

user output
(empty)

Test 8

Group: 3

Verdict:

input
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
229147081

user output
(empty)

Test 9

Group: 3

Verdict:

input
1000
520283 805991 492643 75254 527...

correct output
951147313

user output
(empty)