Submission #959880
Source Code Expand
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
public class Main {
TreeSet<String> all = new TreeSet<>();
ArrayList<TreeSet<String>> andset;
int k, n;
int[] v;
String[] w;
int[][] retro_v;
int[] retro_v_size;
void run() {
dfs(0, 1, "");
dfs(0, 2, "");
dfs(0, 3, "");
k = ni();
andset = new ArrayList<>(k + 1);
for (int i = 0; i <= k; ++i) {
andset.add(new TreeSet<>(all));
}
n = ni();
v = new int[n];
w = new String[n];
for (int i = 0; i < n; ++i) {
v[i] = ni();
w[i] = sc.next();
}
retro_v = new int[n][];
retro_v_size = new int[n];
for (int i = 0; i < n; ++i) { // 5 \times 10
LinkedList<Integer> d = new LinkedList<>();
int u = v[i];
int sz = 0;
while (u > 0) {
int a = u % 10;
d.addFirst(a);
u /= 10;
++sz;
}
int[] e = d.stream().mapToInt(Integer::intValue).toArray();
retro_v[i] = e;
retro_v_size[i] = sz;
TreeSet<Integer> next = new TreeSet<>();
next.add(0);
for (int j = 0; j < sz; ++j) { // 10
TreeSet<String> set = new TreeSet<>();
TreeSet<Integer> nnext = new TreeSet<>();
for (int idx : next) { // 2 \times 10^4
String s = "";
for (int ofs = 0; ofs < 3; ++ofs) {
if (idx + ofs >= w[i].length()) {
continue;
}
s += w[i].charAt(idx + ofs);
set.add(s);
nnext.add(idx + ofs + 1);
}
}
andset.get(e[j]).retainAll(set);
next = nnext;
}
}
check(new String[k + 1], 1);
for (int i = 1; i <= k; ++i) {
System.out.println(ans[i]);
}
}
String[] ans;
boolean check(String[] d, int depth) {
if (depth > k) {
//check
for (int i = 0; i < n; ++i) {
int[] e = retro_v[i];
int sz = retro_v_size[i];
int jndex = 0;
for (int j = 0; j < sz; ++j) {
int v = e[j];
String key = d[v];
for (int l = 0; l < key.length(); ++l) {
if (jndex + l >= w[i].length()) {
return false;
}
if (key.charAt(l) != w[i].charAt(jndex + l)) {
return false;
}
}
jndex += key.length();
}
if (jndex != w[i].length()) {
return false;
}
}
ans = d.clone();
return true;
}
TreeSet<String> set = andset.get(depth);
Iterator<String> ite = set.iterator();
while (ite.hasNext()) {
d[depth] = ite.next();
boolean flag = check(d, depth + 1);
if (flag) {
return true;
}
}
return false;
}
void dfs(int depth, int length, String str) {
if (depth >= length) {
all.add(str);
return;
}
for (char c = 'a'; c <= 'z'; ++c) {
dfs(depth + 1, length, str + c);
}
}
Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
new Main().run();
}
int ni() {
return Integer.parseInt(sc.next());
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
class BIT<T> {
int n;
ArrayList<T> bit;
BiFunction<T, T, T> bif;
/**
* 1-indexed なBinary Indexed Treeを構築する
*
* @param n 容量
* @param bif 適用させる関数
* @param sup 初期値
*/
BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
this.n = n;
bit = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
bit.add(sup.get());
}
this.bif = bif;
}
/**
* iの位置の値をvで更新する
*
* @param i index
* @param v 新しい値
*/
void update(int i, T v) {
for (int x = i; x <= n; x += x & -x) {
bit.set(x, bif.apply(bit.get(x), v));
}
}
/**
* クエリー
*
* @param defaultValue 初期値
* @param i index
* @return [1, i]までfを適用した結果
*/
T reduce(T defaultValue, int i) {
T ret = defaultValue;
for (int x = i; x > 0; x -= x & -x) {
ret = bif.apply(ret, bit.get(x));
}
return ret;
}
}
long MOD = 1_000_000_007;
/**
* 繰り返し2乗法を用いたべき乗の実装
*
* @return a^r (mod 1,000,000,007)
*/
long pow(long a, long r) {
long sum = 1;
while (r > 0) {
if ((r & 1) == 1) {
sum *= a;
sum %= MOD;
}
a *= a;
a %= MOD;
r >>= 1;
}
return sum;
}
/**
* 組み合わせ
* O(n)
*
* @return {}_nC_r
*/
long C(int n, int r) {
long sum = 1;
for (int i = n; 0 < i; --i) {
sum *= i;
sum %= MOD;
}
long s = 1;
for (int i = r; 0 < i; --i) {
s *= i;
s %= MOD;
}
sum *= pow(s, MOD - 2);
sum %= MOD;
long t = 1;
for (int i = n - r; 0 < i; --i) {
t *= i;
t %= MOD;
}
sum *= pow(t, MOD - 2);
sum %= MOD;
return sum;
}
double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
/**
* 黄金分割探索
*
* @param left 下限
* @param right 上限
* @param f 探索する関数
* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
* @return 極値の座標x
*/
double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
double d1 = f.apply(c1);
double d2 = f.apply(c2);
while (right - left > 1e-9) {
if (comp.compare(d1, d2) > 0) {
right = c2;
c2 = c1;
d2 = d1;
c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
d1 = f.apply(c1);
} else {
left = c1;
c1 = c2;
d1 = d2;
c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
d2 = f.apply(c2);
}
}
return right;
}
/**
* [a,b]をm:nに内分する点を返す
*/
double divideInternally(double a, double b, double m, double n) {
return (n * a + m * b) / (m + n);
}
long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
long lcd(long a, long b) {
return (a / gcd(a, b)) * b;
}
int lcd(int a, int b) {
return (a / gcd(a, b)) * b;
}
/**
* http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
*/
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in) {
this.in = in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++];
else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
}
Submission Info
Submission Time |
|
Task |
D - 語呂合わせ |
User |
arukuka |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
9188 Byte |
Status |
AC |
Exec Time |
629 ms |
Memory |
49080 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
40 / 40 |
60 / 60 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
Subtask1 |
sample-02.txt, sample-03.txt, sample-04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt |
Subtask2 |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt |
Case Name |
Status |
Exec Time |
Memory |
sample-01.txt |
AC |
629 ms |
44016 KB |
sample-02.txt |
AC |
482 ms |
41528 KB |
sample-03.txt |
AC |
476 ms |
40808 KB |
sample-04.txt |
AC |
479 ms |
40936 KB |
subtask1-01.txt |
AC |
473 ms |
41816 KB |
subtask1-02.txt |
AC |
488 ms |
41708 KB |
subtask1-03.txt |
AC |
491 ms |
42656 KB |
subtask1-04.txt |
AC |
471 ms |
41924 KB |
subtask1-05.txt |
AC |
482 ms |
41924 KB |
subtask1-06.txt |
AC |
515 ms |
42604 KB |
subtask1-07.txt |
AC |
495 ms |
42256 KB |
subtask1-08.txt |
AC |
489 ms |
42144 KB |
subtask1-09.txt |
AC |
497 ms |
42176 KB |
subtask1-10.txt |
AC |
488 ms |
42408 KB |
subtask1-11.txt |
AC |
511 ms |
43908 KB |
subtask1-12.txt |
AC |
517 ms |
42240 KB |
subtask1-13.txt |
AC |
518 ms |
43832 KB |
subtask1-14.txt |
AC |
505 ms |
42028 KB |
subtask1-15.txt |
AC |
490 ms |
42480 KB |
subtask1-16.txt |
AC |
514 ms |
43768 KB |
subtask1-17.txt |
AC |
495 ms |
41888 KB |
subtask1-18.txt |
AC |
498 ms |
42288 KB |
subtask1-19.txt |
AC |
478 ms |
42296 KB |
subtask1-20.txt |
AC |
483 ms |
42312 KB |
subtask2-01.txt |
AC |
526 ms |
46204 KB |
subtask2-02.txt |
AC |
537 ms |
46480 KB |
subtask2-03.txt |
AC |
539 ms |
46728 KB |
subtask2-04.txt |
AC |
552 ms |
46828 KB |
subtask2-05.txt |
AC |
527 ms |
46996 KB |
subtask2-06.txt |
AC |
524 ms |
46924 KB |
subtask2-07.txt |
AC |
545 ms |
48300 KB |
subtask2-08.txt |
AC |
529 ms |
46932 KB |
subtask2-09.txt |
AC |
551 ms |
48244 KB |
subtask2-10.txt |
AC |
542 ms |
48620 KB |
subtask2-11.txt |
AC |
556 ms |
48820 KB |
subtask2-12.txt |
AC |
528 ms |
47160 KB |
subtask2-13.txt |
AC |
575 ms |
47096 KB |
subtask2-14.txt |
AC |
538 ms |
46704 KB |
subtask2-15.txt |
AC |
546 ms |
46832 KB |
subtask2-16.txt |
AC |
545 ms |
46724 KB |
subtask2-17.txt |
AC |
551 ms |
46828 KB |
subtask2-18.txt |
AC |
615 ms |
48548 KB |
subtask2-19.txt |
AC |
578 ms |
48444 KB |
subtask2-20.txt |
AC |
566 ms |
49080 KB |