— Dark mode

Datatähti 2024 alku

Käännöt

  • Start: 2023-10-30 00:00:00
  • End: 2023-11-13 00:00:00
  • Contest has ended
CSES - Datatähti 2024 alku - Results
Submission details
Task:Käännöt
Sender:andreibe
Submission time:2023-11-06 19:27:09 +0200
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.07 s1details
#20.07 s1details
#30.07 s1details
#40.07 s1details
#50.07 s1details
#60.07 s2details
#70.07 s2details
#80.07 s2details
#90.07 s2details
#100.07 s2details
#110.07 s2details
#120.07 s2details
#130.07 s2details
#140.07 s2details
#150.07 s2details
#160.07 s2details
#170.07 s3details
#180.07 s3details
#190.07 s3details
#200.07 s3details
#210.07 s3details
#220.07 s3details
#230.07 s3details
#240.07 s3details
#250.07 s3details
#260.07 s4details
#270.07 s4details
#280.08 s4details
#290.07 s4details
#300.07 s4details
#310.07 s4details
#320.07 s4details
#330.07 s4details
#340.07 s4details

Code

import java.util.*;
 
public class Main {
    private static boolean isSorted(int[] ar) {
        for (int i = 0; i < ar.length - 1; i++) {
            if (ar[i] < ar[i + 1]) {
                continue;
            }
            return false;
        }
        return true;
    }
    private static class TestCase {
        public int n;
        public int k;
        public int[] ar;
 
        public TestCase(int n, int k, int[] ar) {
            this.n = n;
            this.k = k;
            this.ar = ar;
        }
    }
    private static void swap(int y, int x, int[] ar) {
        int temp = ar[y];
        ar[y] = ar[x];
        ar[x] = temp;
    }
    private static void swapLoc(int y, int x, int[] ar, HashMap<Integer, Integer> locations, boolean log) {
        int temp = ar[y];
        ar[y] = ar[x];
        locations.put(ar[x], y);
        ar[x] = temp;
        locations.put(temp, x);
        if (log) operations.add(y+1);
    }
 
    private static TestCase createTestCase(int k) {
        int n = k * 100;
        int[] ar = new int[n];
        for (int i = 0; i < ar.length; i++) {
            ar[i] = i+1;
        }
        Random random = new Random();
        for (int i = 0; i < 200; i++) {
            int startIndex = random.nextInt(n-k);
            if (k == 4) {
                swap(startIndex, startIndex+3,ar);
                swap(startIndex+1, startIndex+2,ar);
            }
            if (k == 5) {
                swap(startIndex, startIndex+4, ar);
                swap(startIndex+1, startIndex+3, ar);
            }
        }
        //shuffleArray(ar);
        return new TestCase(n,k,ar);
    }
    static boolean tryStupidAlgorithmK4(TestCase testCase, boolean logOperations) {
        int[] ar = testCase.ar;
 
        HashMap<Integer, Integer> location = new HashMap<>();
        int min = 1000;
        for (int j : ar) {
            min = Math.min(min, j);
        }
        for (int i = 0; i < ar.length; i++) {
            ar[i] = ar[i] - min + 1;
            location.put(ar[i], i);
        }
        //System.out.println("After: 0 " + Arrays.toString(ar));
        for (int number = 1; number <= ar.length; number++) {
            int locationNow = location.get(number);
            int locationShouldBe = number - 1;
            //System.out.println("Location of " + number + ": " + locationNow + ". Should be " + locationShouldBe);
            if (locationNow == locationShouldBe) continue;
 
            locationShouldBe += 3;
            boolean exit = false;
            while (locationNow < locationShouldBe) {
                if (locationShouldBe >= ar.length || locationNow + 3 >= ar.length) {
                    exit = true;
                    break;
                }
                //moving right
                swapLoc(locationNow, locationNow+3, ar, location, logOperations);
                swapLoc(locationNow+1, locationNow+2, ar, location, false);
 
                locationNow = locationNow + 3;
            }
            if (exit) continue;
            while (locationNow > locationShouldBe) {
                int diff = locationNow - locationShouldBe;
                if (diff >= 3) {
                    swapLoc(locationNow-3, locationNow, ar, location, logOperations);
                    swapLoc(locationNow-2, locationNow-1, ar, location, false);
                    locationNow -= 3;
                }
                else {
                    if (locationNow + 1 >= ar.length) break;
                    swapLoc(locationNow-2, locationNow+1, ar, location, logOperations);
                    swapLoc(locationNow-1, locationNow, ar, location, false);
                    locationNow -= 1;
                }
            }
            swapLoc(locationNow-3, locationNow, ar, location, logOperations);
            swapLoc(locationNow-2, locationNow-1, ar, location, false);
 
            //System.out.println("After: " + number + " " + Arrays.toString(ar));
        }
        return isSorted(ar);
    }
    static int[] copy;
 
    static ArrayList<Integer> operations = new ArrayList<>();
 
    private static void shuffleArray(int[] array) {
        int index;
        Random random = new Random();
        for (int i = array.length - 1; i > 0; i--)
        {
            index = random.nextInt(i + 1);
            if (index != i)
            {
                array[index] ^= array[i];
                array[i] ^= array[index];
                array[index] ^= array[i];
            }
        }
    }
 
    public static void runTestCases() {
        for (int i = 0; i < 100; i++) {
            TestCase testCase = createTestCase(4);
            int[] original = new int[testCase.ar.length];
            System.arraycopy(testCase.ar, 0, original, 0, original.length);
 
            operations.clear();
            boolean result = test(testCase);
 
            StringBuilder builder = new StringBuilder();
            if (result) {
                checkResult(original, operations, testCase.k);
                System.out.println(true);
 
            } else {
                System.out.println(false);
                builder.append("NO\n");
            }
            //System.out.println(builder);
        }
    }
    private static long startTime = 0;
 
 
    public static void main(String[] args) {
        startTime = System.currentTimeMillis();
 
        TestCase testCase;
        if (args[0].equals("debug")) {
            testCase = createTestCase(4);
        } else {
            Scanner scanner = new Scanner(Objects.requireNonNull(Main.class.getResourceAsStream("/input.txt")));
            String[] line = scanner.nextLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int k = Integer.parseInt(line[1]);
            int[] ar = new int[n];
            line = scanner.nextLine().split(" ");
            for (int i = 0; i < ar.length; i++) {
                ar[i] = Integer.parseInt(line[i]);
            }
            testCase = new TestCase(n,k,ar);
        }
        int k = testCase.k;
        int[] ar = testCase.ar;
        int[] original = new int[ar.length];
        System.arraycopy(ar, 0, original, 0, original.length);
        //tryStupidAlgorithmK4(testCase, false);
        //System.exit(0);
 
        boolean result = false;
        if (k == 4) {
            result = test(testCase);
        }
        if (k == 2) {
            //bubble sort
            while (true) {
                boolean changes = false;
                for (int i = 0; i < ar.length -1; i++) {
                    if (ar[i] > ar[i+1]) {
                        int temp = ar[i];
                        operations.add(i+1);
                        ar[i] = ar[i+1];
                        ar[i+1] = temp;
                        changes = true;
                    }
                }
                if (!changes) break;
            }
            result = true;
        }
        if (k == 3) {
            while (true) {
                boolean changes = false;
                for (int i = 0; i < ar.length-2; i++) {
                    if (ar[i] > ar[i+2]) {
                        int temp = ar[i];
                        operations.add(i+1);
                        ar[i] = ar[i+2];
                        ar[i+2] = temp;
                        changes = true;
                    }
                }
                if (!changes) break;
            }
            result = isSorted(ar);
        }
 
 
 
        StringBuilder builder = new StringBuilder();
        if (result) {
            builder.append("YES\n");
 
            builder.append(operations.size()).append("\n");
            //checkResult(original, operations, testCase.k);
 
            for (Integer operation : operations) {
                builder.append(operation).append(" ");
            }
 
 
        } else {
            builder.append("NO\n");
        }
        System.out.println(builder);
        //System.out.println("Took: " + (System.currentTimeMillis() - startTime));
    }
 
    private static void checkResult(int[] original, ArrayList<Integer> operations, int k) {
        for (int operation : operations) {
            operation--;
            if (k == 4) {
                swap(operation, operation+3, original);
                swap(operation+1, operation+2, original);
            }
            if (k == 5) {
                swap(operation, operation+4, original);
                swap(operation+1, operation+3, original);
            }
        }
        if (!isSorted(original)) {
            throw new IllegalArgumentException("Not sorted " + Arrays.toString(original));
        }
    }
 
    static boolean test(TestCase start) {
        if (start.n > start.k * 8) {
            //System.out.println("WHAT?");
            //sort most of array
            tryStupidAlgorithmK4(start, true);
 
            //System.out.println("After stupid: " +Arrays.toString(start.ar));
 
            int[] ar = start.ar;
            //sort the last k*8 elements separately
            int[] smallerAr = new int[start.k * 8];
            for (int i = 0; i < smallerAr.length; i++) {
                smallerAr[i] = ar[ar.length - smallerAr.length + i];
            }
            ArrayList<Integer> operationsCopy = new ArrayList<>(operations);
            operations.clear();
            //System.out.println("Mid time: " + (System.currentTimeMillis()- startTime) +" operations: " + operationsCopy.size());
            boolean b = test(new TestCase(smallerAr.length, start.k, smallerAr));
            if (b) {
                //System.out.println(operations);
                for (int operation : operations) {
                    operation += (ar.length - smallerAr.length);
                    operationsCopy.add(operation);
                }
            }
            operations = operationsCopy;
 
            return b;
        }
        //System.out.println("32 array: " + Arrays.toString(start.ar));
        copy = new int[start.ar.length];
        Random random = new Random();
        while ((System.currentTimeMillis() - startTime) < 800) {
            int randomIndex = random.nextInt(start.ar.length+1 - start.k);
            operations.add(randomIndex+1);
 
            if (start.k == 4) {
                swap(randomIndex, randomIndex+3, start.ar);
                swap(randomIndex+1, randomIndex+2, start.ar);
            }
            if (start.k == 5) {
                swap(randomIndex, randomIndex+4, start.ar);
                swap(randomIndex+1, randomIndex+3, start.ar);
            }
 
 
            System.arraycopy(start.ar, 0, copy, 0, start.ar.length);
            boolean res = tryStupidAlgorithmK4(new TestCase(start.n, start.k, copy), false);
            if (res) {
                System.arraycopy(start.ar, 0, copy, 0, start.ar.length);
                tryStupidAlgorithmK4(new TestCase(start.n, start.k, copy), true);
                break;
            }
        }
        return isSorted(copy);
        //System.out.println(builder);
        //System.out.println(System.currentTimeMillis() - startTime);
        //System.out.println(operations.size());
    }
}

Test details

Test 1

Group: 1

Verdict:

input
5 2
1 2 3 4 5
view save

correct output
YES
0
view save

user output
(empty)

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

Test 2

Group: 1

Verdict:

input
5 2
2 1 3 4 5
view save

correct output
YES
1
1
view save

user output
(empty)

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

Test 3

Group: 1

Verdict:

input
20 2
6 20 18 2 16 13 19 17 8 14 11 ...
view save

correct output
YES
366
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
(empty)

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

Test 4

Group: 1

Verdict:

input
100 2
100 92 62 88 12 7 43 31 19 72 ...
view save

correct output
YES
2876
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

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

Test 5

Group: 1

Verdict:

input
100 2
100 99 98 97 96 95 94 93 92 91...
view save

correct output
YES
5248
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

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

Test 6

Group: 2

Verdict:

input
5 3
1 2 3 4 5
view save

correct output
YES
0
view save

user output
(empty)

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

Test 7

Group: 2

Verdict:

input
5 3
3 5 4 1 2
view save

correct output
NO
view save

user output
(empty)

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

Test 8

Group: 2

Verdict:

input
5 3
5 2 1 4 3
view save

correct output
YES
8
1 2 1 3 1 2 3 1
view save

user output
(empty)

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

Test 9

Group: 2

Verdict:

input
20 3
19 14 1 18 3 4 11 20 13 6 17 8...
view save

correct output
YES
52
8 10 12 14 16 18 1 3 5 7 9 11 ...
view save

user output
(empty)

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

Test 10

Group: 2

Verdict:

input
20 3
9 6 13 18 5 10 3 2 7 20 1 4 19...
view save

correct output
YES
50
10 12 14 16 18 13 15 17 4 6 8 ...
view save

user output
(empty)

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

Test 11

Group: 2

Verdict:

input
500 3
53 52 21 76 25 142 5 4 83 176 ...
view save

correct output
YES
15194
334 336 338 340 342 344 346 34...
view save

user output
(empty)

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

Test 12

Group: 2

Verdict:

input
500 3
51 44 147 172 1 28 27 82 233 1...
view save

correct output
YES
15565
366 368 370 372 374 376 378 38...
view save

user output
(empty)

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

Test 13

Group: 2

Verdict:

input
500 3
75 46 179 62 221 14 67 154 89 ...
view save

correct output
YES
15920
454 456 458 460 462 464 466 46...
view save

user output
(empty)

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

Test 14

Group: 2

Verdict:

input
500 3
161 54 285 12 71 142 111 94 97...
view save

correct output
YES
15931
408 410 412 414 416 418 420 42...
view save

user output
(empty)

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

Test 15

Group: 2

Verdict:

input
500 3
122 260 455 113 315 276 433 43...
view save

correct output
NO
view save

user output
(empty)

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

Test 16

Group: 2

Verdict:

input
500 3
499 500 497 498 495 496 493 49...
view save

correct output
YES
62264
2 4 6 8 10 12 14 16 18 20 22 2...
view save

user output
(empty)

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

Test 17

Group: 3

Verdict:

input
5 4
1 2 3 4 5
view save

correct output
YES
0
view save

user output
(empty)

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

Test 18

Group: 3

Verdict:

input
5 4
5 1 2 3 4
view save

correct output
YES
4
1 2 1 2
view save

user output
(empty)

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

Test 19

Group: 3

Verdict:

input
500 4
58 14 107 124 4 113 24 290 56 ...
view save

correct output
YES
15698
389 392 395 398 401 404 407 41...
view save

user output
(empty)

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

Test 20

Group: 3

Verdict:

input
500 4
113 187 278 242 23 67 48 298 3...
view save

correct output
YES
15004
480 481 480 482 485 488 491 49...
view save

user output
(empty)

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

Test 21

Group: 3

Verdict:

input
500 4
5 233 199 35 213 354 11 134 30...
view save

correct output
YES
16770
458 461 464 467 470 473 476 47...
view save

user output
(empty)

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

Test 22

Group: 3

Verdict:

input
500 4
169 47 21 137 57 138 360 147 4...
view save

correct output
YES
15889
497 371 372 371 373 376 379 38...
view save

user output
(empty)

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

Test 23

Group: 3

Verdict:

input
500 4
493 409 291 313 156 443 496 40...
view save

correct output
YES
22886
480 481 480 482 485 488 491 49...
view save

user output
(empty)

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

Test 24

Group: 3

Verdict:

input
500 4
137 99 100 226 326 298 140 340...
view save

correct output
NO
view save

user output
(empty)

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

Test 25

Group: 3

Verdict:

input
500 4
500 499 498 497 496 495 494 49...
view save

correct output
YES
41458
1 2 1 2 5 8 11 14 17 20 23 26 ...
view save

user output
(empty)

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

Test 26

Group: 4

Verdict:

input
5 5
1 2 3 4 5
view save

correct output
YES
0
view save

user output
(empty)

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

Test 27

Group: 4

Verdict:

input
5 5
5 4 3 2 1
view save

correct output
YES
1
1
view save

user output
(empty)

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

Test 28

Group: 4

Verdict:

input
500 5
145 26 285 154 147 314 141 40 ...
view save

correct output
YES
13786
216 220 224 228 232 236 240 24...
view save

user output
(empty)

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

Test 29

Group: 4

Verdict:

input
500 5
137 22 399 292 249 6 51 224 42...
view save

correct output
YES
13465
456 460 464 468 472 476 480 48...
view save

user output
(empty)

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

Test 30

Group: 4

Verdict:

input
500 5
153 52 85 100 329 60 433 468 4...
view save

correct output
YES
13642
377 378 377 380 384 388 392 39...
view save

user output
(empty)

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

Test 31

Group: 4

Verdict:

input
500 5
267 326 95 108 189 32 291 366 ...
view save

correct output
YES
14639
213 214 213 216 220 224 228 23...
view save

user output
(empty)

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

Test 32

Group: 4

Verdict:

input
500 5
15 450 272 80 321 101 247 438 ...
view save

correct output
NO
view save

user output
(empty)

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

Test 33

Group: 4

Verdict:

input
499 5
497 498 499 496 495 494 493 49...
view save

correct output
YES
30886
3 7 11 15 19 23 27 31 35 39 43...
view save

user output
(empty)

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

Test 34

Group: 4

Verdict:

input
500 5
499 500 497 498 495 496 493 49...
view save

correct output
YES
30919
1 4 8 12 16 20 24 28 32 36 40 ...
view save

user output
(empty)

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

Tasks

A Lumimyrsky-B Monistus-C Laskettelukeskus-D Uolevin kalansaalis-E Käännöt-F Säähavainnot-

Submissions (andreibe)

2023-11-06 20:01:32 1002023-11-06 20:00:45 682023-11-06 19:59:37 352023-11-06 19:42:11 652023-11-06 19:27:47 652023-11-06 19:27:09 02023-11-06 17:58:14 322023-11-06 17:57:26 322023-11-06 17:56:18 322023-11-06 17:55:12 2023-11-04 13:47:31 32