Submission #58871


Source Code Expand

import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int A, B;
	static long[] table = new long[50];
	static HashMap<Integer, String> map = new HashMap<Integer, String>();
	static int memoLen = 4;

	static void memo(char[] buf, int pos, long hash) {
		if (pos == memoLen) {
			//			System.out.println(hash + " " + (long)hash(String.valueOf(buf)) * A % B);
			map.put((int) hash, String.valueOf(buf));
			return;
		}
		for (int i = 0; i < 26; ++i) {
			buf[pos] = (char) (i + 'a');
			memo(buf, pos + 1, (hash + table[memoLen - pos] * (i + 1)) % B);
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		A = sc.nextInt();
		B = sc.nextInt();
		table[0] = 1;
		for (int i = 1; i < table.length; ++i) {
			table[i] = table[i - 1] * A % B;
		}
		{
			char[] buf = new char[memoLen];
			memo(buf, 0, 0);
		}

		HashSet<String> ans = new HashSet<String>();
		Random rand = new Random();
		char[] buf = new char[40];
		while (ans.size() < 100 && System.currentTimeMillis() - start < 1400) {
			long hash = 0;
			for (int i = 0; i < buf.length; ++i) {
				int v = rand.nextInt(26);
				hash += (v + 1) * table[i + memoLen + 1];
				hash %= B;
				buf[buf.length - 1 - i] = (char) (v + 'a');
			}
//			System.out.println(hash + " " + (long) hash(String.valueOf(buf)) * table[memoLen + 1] % B);
			for (int i = 1; i <= 26; ++i) {
				int key = (int) (B - hash - i);
				if (key < 0) key += B;
				if (map.containsKey(key)) {
					String suf = map.get(key);
					ans.add(String.valueOf(buf) + suf + (char) (i - 1 + 'a'));
					if (ans.size() == 100) break;
				}
			}
		}
		for (String s : ans) {
//			System.out.println(hash(s));
			System.out.println(s);
		}
	}

	static int hash(String s) {
		long h = 0;
		for (int i = 0; i < s.length(); ++i) {
			h = (h * A + (s.charAt(i) - 'a' + 1)) % B;
		}
		return (int) h;
	}

}

Submission Info

Submission Time
Task F - Uinny
User tomerun
Language Java (OpenJDK 1.7.0)
Score 190
Code Size 2052 Byte
Status AC
Exec Time 1986 ms
Memory 110288 KB

Judge Result

Set Name 010_01 010_02 010_03 010_04 010_05 010_06 010_07 010_08 010_09 010_10 010_11 010_12 010_13 010_14 010_15 010_16 010_17 010_18 010_19 010_20 010_21 010_22 010_23 010_24 010_25 010_26 010_27 010_28 010_29 010_30 010_31 010_32 010_33 010_34 010_35 010_36 010_37 010_38 010_39 010_40 010_41 010_42 010_43 010_44 010_45 010_46 010_47 010_48 010_49 010_50 010_51 010_52 010_53 010_54 010_55 010_56 010_57 010_58 010_59 010_60 010_61 010_62 010_63 010_64 010_65 010_66 010_67 010_68 010_69 010_70 010_71 010_72 010_73 010_74 010_75 010_76 010_77 010_78 010_79 010_80 010_81 010_82 010_83 010_84 010_85 010_86 010_87 010_88 010_89 010_90 010_91 010_92 010_93 010_94 010_95 010_96 010_97 010_98 010_99 sample
Score / Max Score 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 2 / 2 0 / 2 2 / 2 2 / 2 2 / 2 2 / 2
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
010_01 010_01.txt
010_02 010_02.txt
010_03 010_03.txt
010_04 010_04.txt
010_05 010_05.txt
010_06 010_06.txt
010_07 010_07.txt
010_08 010_08.txt
010_09 010_09.txt
010_10 010_10.txt
010_11 010_11.txt
010_12 010_12.txt
010_13 010_13.txt
010_14 010_14.txt
010_15 010_15.txt
010_16 010_16.txt
010_17 010_17.txt
010_18 010_18.txt
010_19 010_19.txt
010_20 010_20.txt
010_21 010_21.txt
010_22 010_22.txt
010_23 010_23.txt
010_24 010_24.txt
010_25 010_25.txt
010_26 010_26.txt
010_27 010_27.txt
010_28 010_28.txt
010_29 010_29.txt
010_30 010_30.txt
010_31 010_31.txt
010_32 010_32.txt
010_33 010_33.txt
010_34 010_34.txt
010_35 010_35.txt
010_36 010_36.txt
010_37 010_37.txt
010_38 010_38.txt
010_39 010_39.txt
010_40 010_40.txt
010_41 010_41.txt
010_42 010_42.txt
010_43 010_43.txt
010_44 010_44.txt
010_45 010_45.txt
010_46 010_46.txt
010_47 010_47.txt
010_48 010_48.txt
010_49 010_49.txt
010_50 010_50.txt
010_51 010_51.txt
010_52 010_52.txt
010_53 010_53.txt
010_54 010_54.txt
010_55 010_55.txt
010_56 010_56.txt
010_57 010_57.txt
010_58 010_58.txt
010_59 010_59.txt
010_60 010_60.txt
010_61 010_61.txt
010_62 010_62.txt
010_63 010_63.txt
010_64 010_64.txt
010_65 010_65.txt
010_66 010_66.txt
010_67 010_67.txt
010_68 010_68.txt
010_69 010_69.txt
010_70 010_70.txt
010_71 010_71.txt
010_72 010_72.txt
010_73 010_73.txt
010_74 010_74.txt
010_75 010_75.txt
010_76 010_76.txt
010_77 010_77.txt
010_78 010_78.txt
010_79 010_79.txt
010_80 010_80.txt
010_81 010_81.txt
010_82 010_82.txt
010_83 010_83.txt
010_84 010_84.txt
010_85 010_85.txt
010_86 010_86.txt
010_87 010_87.txt
010_88 010_88.txt
010_89 010_89.txt
010_90 010_90.txt
010_91 010_91.txt
010_92 010_92.txt
010_93 010_93.txt
010_94 010_94.txt
010_95 010_95.txt
010_96 010_96.txt
010_97 010_97.txt
010_98 010_98.txt
010_99 010_99.txt
sample sample.txt
Case Name Status Exec Time Memory
010_01.txt AC 1560 ms 83192 KB
010_02.txt AC 1430 ms 83300 KB
010_03.txt AC 1551 ms 83732 KB
010_04.txt AC 1499 ms 82808 KB
010_05.txt AC 1500 ms 83144 KB
010_06.txt AC 1520 ms 83148 KB
010_07.txt AC 1531 ms 83348 KB
010_08.txt AC 1372 ms 83404 KB
010_09.txt AC 1670 ms 83464 KB
010_10.txt AC 1986 ms 110288 KB
010_11.txt AC 1552 ms 83204 KB
010_12.txt AC 1544 ms 83472 KB
010_13.txt AC 1425 ms 83148 KB
010_14.txt AC 1918 ms 96960 KB
010_15.txt AC 1445 ms 84040 KB
010_16.txt AC 1400 ms 83652 KB
010_17.txt AC 1773 ms 82904 KB
010_18.txt AC 1567 ms 83252 KB
010_19.txt AC 1664 ms 83028 KB
010_20.txt AC 1550 ms 85084 KB
010_21.txt AC 1541 ms 82928 KB
010_22.txt AC 1909 ms 94800 KB
010_23.txt AC 1617 ms 83060 KB
010_24.txt AC 1499 ms 83368 KB
010_25.txt AC 1619 ms 82992 KB
010_26.txt AC 1611 ms 83208 KB
010_27.txt AC 1506 ms 83344 KB
010_28.txt AC 1430 ms 83156 KB
010_29.txt AC 1605 ms 83548 KB
010_30.txt AC 1517 ms 83432 KB
010_31.txt AC 1493 ms 83284 KB
010_32.txt AC 1649 ms 83668 KB
010_33.txt AC 1540 ms 83444 KB
010_34.txt AC 1525 ms 83092 KB
010_35.txt AC 1465 ms 83844 KB
010_36.txt AC 1411 ms 83256 KB
010_37.txt AC 1344 ms 83536 KB
010_38.txt AC 1476 ms 83372 KB
010_39.txt AC 1438 ms 83600 KB
010_40.txt AC 1542 ms 83072 KB
010_41.txt AC 1611 ms 83292 KB
010_42.txt AC 1548 ms 83184 KB
010_43.txt AC 1393 ms 83412 KB
010_44.txt AC 1600 ms 83340 KB
010_45.txt AC 1559 ms 83016 KB
010_46.txt AC 1633 ms 83736 KB
010_47.txt AC 1544 ms 83472 KB
010_48.txt AC 1660 ms 83344 KB
010_49.txt AC 1499 ms 83792 KB
010_50.txt AC 1494 ms 82964 KB
010_51.txt AC 1546 ms 83204 KB
010_52.txt AC 1418 ms 83220 KB
010_53.txt AC 1455 ms 83572 KB
010_54.txt AC 1404 ms 82828 KB
010_55.txt AC 1514 ms 83280 KB
010_56.txt AC 1446 ms 83136 KB
010_57.txt AC 1388 ms 83224 KB
010_58.txt AC 1489 ms 83188 KB
010_59.txt AC 1485 ms 83720 KB
010_60.txt AC 1482 ms 83724 KB
010_61.txt AC 1465 ms 82912 KB
010_62.txt AC 1333 ms 83052 KB
010_63.txt AC 1545 ms 83708 KB
010_64.txt AC 1383 ms 83588 KB
010_65.txt AC 1491 ms 83180 KB
010_66.txt AC 1341 ms 83260 KB
010_67.txt AC 1384 ms 83436 KB
010_68.txt AC 1429 ms 83196 KB
010_69.txt AC 1475 ms 82972 KB
010_70.txt AC 1421 ms 83172 KB
010_71.txt AC 1438 ms 82864 KB
010_72.txt AC 1497 ms 83148 KB
010_73.txt AC 1879 ms 109976 KB
010_74.txt AC 1411 ms 83264 KB
010_75.txt AC 1362 ms 83428 KB
010_76.txt AC 1337 ms 83300 KB
010_77.txt AC 1369 ms 83092 KB
010_78.txt AC 1539 ms 84556 KB
010_79.txt AC 1530 ms 83136 KB
010_80.txt AC 1344 ms 83328 KB
010_81.txt AC 1473 ms 83412 KB
010_82.txt AC 1446 ms 84012 KB
010_83.txt AC 1483 ms 83452 KB
010_84.txt AC 1457 ms 83092 KB
010_85.txt AC 1535 ms 83600 KB
010_86.txt AC 1413 ms 83796 KB
010_87.txt AC 1502 ms 83100 KB
010_88.txt AC 1545 ms 83228 KB
010_89.txt AC 1362 ms 83568 KB
010_90.txt AC 1403 ms 82972 KB
010_91.txt AC 1391 ms 83220 KB
010_92.txt AC 1359 ms 82832 KB
010_93.txt AC 1305 ms 83276 KB
010_94.txt AC 1362 ms 83412 KB
010_95.txt AC 1319 ms 82868 KB
010_96.txt AC 1854 ms 110264 KB
010_97.txt AC 1305 ms 82948 KB
010_98.txt AC 1327 ms 83292 KB
010_99.txt AC 1305 ms 82880 KB
sample.txt AC 561 ms 30604 KB