Task: | Käännöt |
Sender: | andreibe |
Submission time: | 2023-11-06 20:01:32 +0200 |
Language: | Java |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 19 |
#3 | ACCEPTED | 33 |
#4 | ACCEPTED | 35 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.13 s | 1 | details |
#2 | ACCEPTED | 0.13 s | 1 | details |
#3 | ACCEPTED | 0.13 s | 1 | details |
#4 | ACCEPTED | 0.14 s | 1 | details |
#5 | ACCEPTED | 0.15 s | 1 | details |
#6 | ACCEPTED | 0.13 s | 2 | details |
#7 | ACCEPTED | 0.13 s | 2 | details |
#8 | ACCEPTED | 0.13 s | 2 | details |
#9 | ACCEPTED | 0.13 s | 2 | details |
#10 | ACCEPTED | 0.13 s | 2 | details |
#11 | ACCEPTED | 0.20 s | 2 | details |
#12 | ACCEPTED | 0.20 s | 2 | details |
#13 | ACCEPTED | 0.20 s | 2 | details |
#14 | ACCEPTED | 0.20 s | 2 | details |
#15 | ACCEPTED | 0.16 s | 2 | details |
#16 | ACCEPTED | 0.22 s | 2 | details |
#17 | ACCEPTED | 0.13 s | 3 | details |
#18 | ACCEPTED | 0.13 s | 3 | details |
#19 | ACCEPTED | 0.20 s | 3 | details |
#20 | ACCEPTED | 0.20 s | 3 | details |
#21 | ACCEPTED | 0.21 s | 3 | details |
#22 | ACCEPTED | 0.21 s | 3 | details |
#23 | ACCEPTED | 0.21 s | 3 | details |
#24 | ACCEPTED | 0.87 s | 3 | details |
#25 | ACCEPTED | 0.23 s | 3 | details |
#26 | ACCEPTED | 0.13 s | 4 | details |
#27 | ACCEPTED | 0.13 s | 4 | details |
#28 | ACCEPTED | 0.20 s | 4 | details |
#29 | ACCEPTED | 0.20 s | 4 | details |
#30 | ACCEPTED | 0.18 s | 4 | details |
#31 | ACCEPTED | 0.20 s | 4 | details |
#32 | ACCEPTED | 0.14 s | 4 | details |
#33 | ACCEPTED | 0.23 s | 4 | details |
#34 | ACCEPTED | 0.23 s | 4 | details |
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 tryStupidAlgorithmK5(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);}for (int number = 1; number <= ar.length; number++) {int locationNow = location.get(number);int locationShouldBe = number - 1;if (locationNow == locationShouldBe) continue;locationShouldBe += 4;boolean exit = false;while (locationNow < locationShouldBe) {if (locationShouldBe >= ar.length || locationNow + 4 >= ar.length) {exit = true;break;}//moving rightswapLoc(locationNow, locationNow+4, ar, location, logOperations);swapLoc(locationNow+1, locationNow+3, ar, location, false);locationNow = locationNow + 4;}if (exit) continue;exit = false;while (locationNow > locationShouldBe) {int diff = locationNow - locationShouldBe;if (diff >= 4) {swapLoc(locationNow-4, locationNow, ar, location, logOperations);swapLoc(locationNow-3, locationNow-1, ar, location, false);locationNow -= 4;}else {//TODO thisif (locationNow + 1 >= ar.length) {exit = true;break;}swapLoc(locationNow-3, locationNow+1, ar, location, logOperations);swapLoc(locationNow-2, locationNow, ar, location, false);locationNow -= 2;}}if (!exit && locationNow != locationShouldBe) {System.out.println("NO\n");System.exit(0);}swapLoc(locationNow-4, locationNow, ar, location, logOperations);swapLoc(locationNow-3, locationNow-1, ar, location, false);}return isSorted(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 rightswapLoc(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(5);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(Arrays.toString(original));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.length > 0 && args[0].equals("debug")) {testCase = createTestCase(5);} 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 || k == 5) {result = test(testCase);}if (k == 2) {//bubble sortwhile (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 arrayif (start.k == 4) {tryStupidAlgorithmK4(start, true);} else {tryStupidAlgorithmK5(start, true);}//System.out.println("After stupid: " +Arrays.toString(start.ar));int[] ar = start.ar;//sort the last k*8 elements separatelyint[] 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("SUCCESS!");//System.out.println(operations);for (int operation : operations) {operation += (ar.length - smallerAr.length);operationsCopy.add(operation);}}operations = operationsCopy;return b;}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;if (start.k == 4) {res = tryStupidAlgorithmK4(new TestCase(start.n, start.k, copy), false);} else {res = tryStupidAlgorithmK5(new TestCase(start.n, start.k, copy), false);}if (res) {//System.out.println("Omg is sorted?");System.arraycopy(start.ar, 0, copy, 0, start.ar.length);if (start.k == 4) {tryStupidAlgorithmK4(new TestCase(start.n, start.k, copy), true);} else {tryStupidAlgorithmK5(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: ACCEPTED
input |
---|
5 2 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
5 2 2 1 3 4 5 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 1 1 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
20 2 6 20 18 2 16 13 19 17 8 14 11 ... |
correct output |
---|
YES 366 2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
YES 132 2 3 4 5 6 7 8 9 10 11 12 13 14... Truncated |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 92 62 88 12 7 43 31 19 72 ... |
correct output |
---|
YES 2876 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 2438 1 2 3 4 5 6 7 8 9 10 11 12 13 ... Truncated |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 99 98 97 96 95 94 93 92 91... |
correct output |
---|
YES 5248 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 4950 1 2 3 4 5 6 7 8 9 10 11 12 13 ... Truncated |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 3 5 4 1 2 |
correct output |
---|
NO |
user output |
---|
NO |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 5 2 1 4 3 |
correct output |
---|
YES 8 1 2 1 3 1 2 3 1 |
user output |
---|
YES 2 1 3 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 19 14 1 18 3 4 11 20 13 6 17 8... |
correct output |
---|
YES 52 8 10 12 14 16 18 1 3 5 7 9 11 ... |
user output |
---|
YES 42 1 3 4 5 7 8 9 10 11 12 13 14 1... Truncated |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 9 6 13 18 5 10 3 2 7 20 1 4 19... |
correct output |
---|
YES 50 10 12 14 16 18 13 15 17 4 6 8 ... |
user output |
---|
YES 34 3 4 5 6 7 9 10 12 13 14 15 16 ... |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 53 52 21 76 25 142 5 4 83 176 ... |
correct output |
---|
YES 15194 334 336 338 340 342 344 346 34... |
user output |
---|
YES 15174 1 3 5 6 10 11 12 13 14 15 16 1... Truncated |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 51 44 147 172 1 28 27 82 233 1... |
correct output |
---|
YES 15565 366 368 370 372 374 376 378 38... |
user output |
---|
YES 15543 3 4 5 6 8 10 11 12 13 15 16 17... Truncated |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 75 46 179 62 221 14 67 154 89 ... |
correct output |
---|
YES 15920 454 456 458 460 462 464 466 46... |
user output |
---|
YES 15902 4 5 7 9 10 11 12 13 14 15 16 1... Truncated |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 161 54 285 12 71 142 111 94 97... |
correct output |
---|
YES 15931 408 410 412 414 416 418 420 42... |
user output |
---|
YES 15907 2 3 5 6 7 8 9 10 11 13 15 16 1... Truncated |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 122 260 455 113 315 276 433 43... |
correct output |
---|
NO |
user output |
---|
NO |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 62264 2 4 6 8 10 12 14 16 18 20 22 2... |
user output |
---|
YES 62250 1 2 3 4 5 6 7 8 9 10 11 12 13 ... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
5 4 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 2 1 1 |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
5 4 5 1 2 3 4 |
correct output |
---|
YES 4 1 2 1 2 |
user output |
---|
YES 18 1 1 2 1 2 2 1 1 1 2 1 1 2 1 2 ... |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 58 14 107 124 4 113 24 290 56 ... |
correct output |
---|
YES 15698 389 392 395 398 401 404 407 41... |
user output |
---|
YES 14736 24 21 18 15 12 9 6 4 3 1 17 14... Truncated |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 113 187 278 242 23 67 48 298 3... |
correct output |
---|
YES 15004 480 481 480 482 485 488 491 49... |
user output |
---|
YES 13820 265 262 259 256 253 250 247 24... Truncated |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 5 233 199 35 213 354 11 134 30... |
correct output |
---|
YES 16770 458 461 464 467 470 473 476 47... |
user output |
---|
YES 15485 227 224 221 218 215 212 209 20... Truncated |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 169 47 21 137 57 138 360 147 4... |
correct output |
---|
YES 15889 497 371 372 371 373 376 379 38... |
user output |
---|
YES 14796 58 55 52 49 46 43 40 37 34 31 ... Truncated |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 493 409 291 313 156 443 496 40... |
correct output |
---|
YES 22886 480 481 480 482 485 488 491 49... |
user output |
---|
YES 21808 338 335 332 329 326 323 320 31... Truncated |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 137 99 100 226 326 298 140 340... |
correct output |
---|
NO |
user output |
---|
NO |
Test 25
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 500 499 498 497 496 495 494 49... |
correct output |
---|
YES 41458 1 2 1 2 5 8 11 14 17 20 23 26 ... |
user output |
---|
YES 41847 497 494 491 488 485 482 479 47... Truncated |
Test 26
Group: 4
Verdict: ACCEPTED
input |
---|
5 5 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 2 1 1 |
Test 27
Group: 4
Verdict: ACCEPTED
input |
---|
5 5 5 4 3 2 1 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 1 1 |
Test 28
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 145 26 285 154 147 314 141 40 ... |
correct output |
---|
YES 13786 216 220 224 228 232 236 240 24... |
user output |
---|
YES 13242 81 77 73 69 65 61 57 53 49 45 ... Truncated |
Test 29
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 137 22 399 292 249 6 51 224 42... |
correct output |
---|
YES 13465 456 460 464 468 472 476 480 48... |
user output |
---|
YES 13039 467 463 459 455 451 447 443 43... Truncated |
Test 30
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 153 52 85 100 329 60 433 468 4... |
correct output |
---|
YES 13642 377 378 377 380 384 388 392 39... |
user output |
---|
YES 13012 203 199 195 191 187 183 179 17... Truncated |
Test 31
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 267 326 95 108 189 32 291 366 ... |
correct output |
---|
YES 14639 213 214 213 216 220 224 228 23... |
user output |
---|
YES 13983 361 357 353 349 345 341 337 33... Truncated |
Test 32
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 15 450 272 80 321 101 247 438 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 33
Group: 4
Verdict: ACCEPTED
input |
---|
499 5 497 498 499 496 495 494 493 49... |
correct output |
---|
YES 30886 3 7 11 15 19 23 27 31 35 39 43... |
user output |
---|
YES 31192 495 491 487 483 479 475 471 46... Truncated |
Test 34
Group: 4
Verdict: ACCEPTED
input |
---|
500 5 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 30919 1 4 8 12 16 20 24 28 32 36 40 ... |
user output |
---|
YES 31309 495 491 487 483 479 475 471 46... Truncated |