Submission #1017393
Source Code Expand
// package atcoder.other2016.codefestival2016.round1; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.Comparator; import java.util.InputMismatchException; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int k = in.nextInt(); char[] s = in.nextToken().toCharArray(); int n = s.length; int req = s.length / (k+1); int mod = s.length - req * (k+1); if (s.length % (k+1) == 0) { out.println(solveEven(s, k)); out.flush(); return; } SuffixArray sa = new SuffixArray(s); sa.buildSA(); int ng = 0; int ok = n; while (ok - ng > 1) { int med = (ok + ng) / 2; int now = 0; int mkmod = 0; while (now < n) { if (mkmod < mod) { if (sa.rank[now] <= med) { mkmod++; now += req+1; } else { now += req; } } else { now += req; } } if (mkmod == mod && now == n) { ok = med; } else { ng = med; } } int from = sa.sa[ok]; out.println(String.valueOf(s).substring(from, from+req+1)); out.flush(); } private static String solveEven(char[] s, int k) { int n = s.length; int per = n / (k+1); SuffixArray sa = new SuffixArray(s); sa.buildSA(); for (int i = n-1 ; i >= 0 ; i--) { int pt = sa.sa[i+1]; if (pt % per == 0) { return String.valueOf(s).substring(pt, pt+per); } } return ""; } static class SuffixArray { int n; char[] base; Integer[] sa; int[] rank; int[] tmp; int[] lcp; int compareNode(int i, int j, int k) { if (rank[i] != rank[j]) { return rank[i] - rank[j]; } else { int ri = i + k <= n ? rank[i+k] : -1; int rj = j + k <= n ? rank[j+k] : -1; return ri - rj; } } public SuffixArray(char[] x) { base = x; n = base.length; } void buildSA() { sa = new Integer[n+1]; rank = new int[n+1]; tmp = new int[n+1]; for (int i = 0 ; i <= n ; i++) { sa[i] = i; rank[i] = (i < n) ? base[i] : -1; } for (int _k = 1 ; _k <= n ; _k *= 2) { final int k = _k; Arrays.sort(sa, new Comparator<Integer>() { @Override public int compare(Integer i, Integer j) { return compareNode(i, j, k); } }); tmp[sa[0]] = 0; for (int i = 1 ; i <= n ; i++) { tmp[sa[i]] = tmp[sa[i-1]] + ((compareNode(sa[i-1], sa[i], k) < 0) ? 1 : 0); } for (int i = 0 ; i <= n ; i++) { rank[i] = tmp[i]; } } } void buildLCP() { for (int i = 0 ; i <= n ; i++) { rank[sa[i]] = i; } lcp = new int[n]; int h = 0; for (int i = 0 ; i < n ; i++) { int j = sa[rank[i]-1]; if (h > 0) { h--; } for (; j + h < n && i + h < n ; h++) { if (base[j+h] != base[i+h]) { break; } } lcp[rank[i]-1] = h; } } } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int[] nextInts(int n) { int[] ret = new int[n]; for (int i = 0; i < n; i++) { ret[i] = nextInt(); } return ret; } private int[][] nextIntTable(int n, int m) { int[][] ret = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret[i][j] = nextInt(); } } return ret; } private long[] nextLongs(int n) { long[] ret = new long[n]; for (int i = 0; i < n; i++) { ret[i] = nextLong(); } return ret; } private long[][] nextLongTable(int n, int m) { long[][] ret = new long[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret[i][j] = nextLong(); } } return ret; } private double[] nextDoubles(int n) { double[] ret = new double[n]; for (int i = 0; i < n; i++) { ret[i] = nextDouble(); } return ret; } private int next() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { int c = next(); while (isSpaceChar(c)) c = next(); if ('a' <= c && c <= 'z') { return (char) c; } if ('A' <= c && c <= 'Z') { return (char) c; } throw new InputMismatchException(); } public String nextToken() { int c = next(); while (isSpaceChar(c)) c = next(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { int c = next(); while (isSpaceChar(c)) c = next(); int sgn = 1; if (c == '-') { sgn = -1; c = next(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res*sgn; } public long nextLong() { int c = next(); while (isSpaceChar(c)) c = next(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c-'0'; c = next(); } while (!isSpaceChar(c)); return res*sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1000 |
Code Size | 8547 Byte |
Status | AC |
Exec Time | 410 ms |
Memory | 16392 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 100 / 100 | 200 / 200 | 200 / 200 | 400 / 400 | ||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset1 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt |
Dataset2 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt |
Dataset3 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset4 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt |
Dataset5 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 99 ms | 8400 KB |
subtask_01_02.txt | AC | 99 ms | 8396 KB |
subtask_01_03.txt | AC | 98 ms | 8400 KB |
subtask_01_04.txt | AC | 96 ms | 8400 KB |
subtask_01_05.txt | AC | 98 ms | 8400 KB |
subtask_01_06.txt | AC | 98 ms | 8400 KB |
subtask_01_07.txt | AC | 98 ms | 8396 KB |
subtask_01_08.txt | AC | 96 ms | 8396 KB |
subtask_01_09.txt | AC | 99 ms | 8396 KB |
subtask_01_10.txt | AC | 98 ms | 8400 KB |
subtask_01_11.txt | AC | 98 ms | 8400 KB |
subtask_01_12.txt | AC | 99 ms | 8396 KB |
subtask_01_13.txt | AC | 99 ms | 8404 KB |
subtask_01_14.txt | AC | 99 ms | 8396 KB |
subtask_01_15.txt | AC | 97 ms | 8404 KB |
subtask_01_16.txt | AC | 100 ms | 8400 KB |
subtask_01_17.txt | AC | 98 ms | 8396 KB |
subtask_02_01.txt | AC | 99 ms | 8400 KB |
subtask_02_02.txt | AC | 98 ms | 8396 KB |
subtask_02_03.txt | AC | 98 ms | 8400 KB |
subtask_02_04.txt | AC | 98 ms | 8400 KB |
subtask_02_05.txt | AC | 98 ms | 8400 KB |
subtask_02_06.txt | AC | 98 ms | 8400 KB |
subtask_02_07.txt | AC | 96 ms | 8396 KB |
subtask_02_08.txt | AC | 99 ms | 8400 KB |
subtask_02_09.txt | AC | 98 ms | 8400 KB |
subtask_02_10.txt | AC | 98 ms | 8396 KB |
subtask_02_11.txt | AC | 97 ms | 8400 KB |
subtask_02_12.txt | AC | 98 ms | 8400 KB |
subtask_02_13.txt | AC | 98 ms | 8396 KB |
subtask_02_14.txt | AC | 98 ms | 8400 KB |
subtask_02_ex1.txt | AC | 97 ms | 8396 KB |
subtask_03_01.txt | AC | 100 ms | 8396 KB |
subtask_03_02.txt | AC | 98 ms | 8276 KB |
subtask_03_03.txt | AC | 99 ms | 8400 KB |
subtask_03_04.txt | AC | 97 ms | 8400 KB |
subtask_03_05.txt | AC | 98 ms | 8404 KB |
subtask_03_06.txt | AC | 99 ms | 8276 KB |
subtask_03_07.txt | AC | 98 ms | 8400 KB |
subtask_03_08.txt | AC | 98 ms | 8404 KB |
subtask_03_09.txt | AC | 99 ms | 8404 KB |
subtask_03_10.txt | AC | 101 ms | 8400 KB |
subtask_03_11.txt | AC | 99 ms | 8400 KB |
subtask_03_12.txt | AC | 98 ms | 8404 KB |
subtask_03_13.txt | AC | 99 ms | 8396 KB |
subtask_03_14.txt | AC | 99 ms | 8404 KB |
subtask_03_15.txt | AC | 98 ms | 8400 KB |
subtask_03_ex2.txt | AC | 98 ms | 8404 KB |
subtask_03_ex3.txt | AC | 100 ms | 8396 KB |
subtask_04_01.txt | AC | 113 ms | 8528 KB |
subtask_04_02.txt | AC | 112 ms | 8528 KB |
subtask_04_03.txt | AC | 113 ms | 8660 KB |
subtask_04_04.txt | AC | 112 ms | 8528 KB |
subtask_04_05.txt | AC | 111 ms | 8532 KB |
subtask_04_06.txt | AC | 111 ms | 8660 KB |
subtask_04_07.txt | AC | 112 ms | 8528 KB |
subtask_04_08.txt | AC | 112 ms | 8528 KB |
subtask_04_09.txt | AC | 112 ms | 8528 KB |
subtask_04_10.txt | AC | 113 ms | 8916 KB |
subtask_04_11.txt | AC | 108 ms | 8532 KB |
subtask_04_12.txt | AC | 109 ms | 8528 KB |
subtask_04_13.txt | AC | 104 ms | 8532 KB |
subtask_04_14.txt | AC | 112 ms | 8276 KB |
subtask_04_15.txt | AC | 107 ms | 8400 KB |
subtask_05_01.txt | AC | 387 ms | 15844 KB |
subtask_05_02.txt | AC | 367 ms | 15712 KB |
subtask_05_03.txt | AC | 361 ms | 15768 KB |
subtask_05_04.txt | AC | 349 ms | 15844 KB |
subtask_05_05.txt | AC | 382 ms | 15820 KB |
subtask_05_06.txt | AC | 392 ms | 16256 KB |
subtask_05_07.txt | AC | 360 ms | 15696 KB |
subtask_05_08.txt | AC | 358 ms | 15888 KB |
subtask_05_09.txt | AC | 381 ms | 16392 KB |
subtask_05_10.txt | AC | 410 ms | 16108 KB |
subtask_05_11.txt | AC | 200 ms | 13904 KB |
subtask_05_12.txt | AC | 206 ms | 14160 KB |
subtask_05_13.txt | AC | 300 ms | 14700 KB |
subtask_05_14.txt | AC | 339 ms | 15600 KB |
subtask_05_15.txt | AC | 229 ms | 13412 KB |