結果
問題 | No.97 最大の値を求めるくえり |
ユーザー | uwi |
提出日時 | 2014-12-09 04:10:07 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 559 ms / 5,000 ms |
コード長 | 3,160 bytes |
コンパイル時間 | 3,132 ms |
コンパイル使用メモリ | 87,800 KB |
実行使用メモリ | 50,160 KB |
最終ジャッジ日時 | 2024-06-11 18:47:05 |
合計ジャッジ時間 | 10,964 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 75 ms
37,928 KB |
testcase_01 | AC | 101 ms
40,300 KB |
testcase_02 | AC | 556 ms
44,764 KB |
testcase_03 | AC | 559 ms
44,560 KB |
testcase_04 | AC | 224 ms
46,632 KB |
testcase_05 | AC | 236 ms
47,044 KB |
testcase_06 | AC | 259 ms
48,576 KB |
testcase_07 | AC | 356 ms
49,456 KB |
testcase_08 | AC | 340 ms
50,160 KB |
testcase_09 | AC | 428 ms
44,932 KB |
testcase_10 | AC | 504 ms
44,852 KB |
testcase_11 | AC | 413 ms
48,792 KB |
testcase_12 | AC | 474 ms
50,100 KB |
testcase_13 | AC | 397 ms
50,016 KB |
testcase_14 | AC | 355 ms
49,508 KB |
testcase_15 | AC | 287 ms
49,388 KB |
testcase_16 | AC | 266 ms
49,396 KB |
testcase_17 | AC | 252 ms
46,836 KB |
testcase_18 | AC | 290 ms
49,004 KB |
ソースコード
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int n = ni(), Q = ni(); long[] a = new long[n]; XorShift xs = new XorShift(); for(int i = 0;i < n;i++){ a[i] = modh(xs.next()); } if((long)n*n < 300000){ for(int i = 0;i < Q;i++){ int q = ni(); long max = -1; for(int j = 0;j < n;j++){ long v = modh(a[j]*q); if(v > max)max = v; } out.println(max); } }else{ boolean[] table = new boolean[100003]; for(int i = 0;i < n;i++){ table[(int)a[i]] = true; } int[] invs = enumInvs(100002, 100003); for(int i = 0;i < Q;i++){ int q = ni(); if(q == 0){ out.println(0); }else{ int iv = invs[q]; for(int j = 100002;j >= 0;j--){ if(table[(int)modh((long)j*iv)]){ out.println(j); break; } } } } } } public static int mod; public static long M; public static int h; static { mod = 100003; long K = Integer.highestOneBit(mod)<<1; h = Long.numberOfTrailingZeros(K)*2; M = K*K/mod; } public static long modh(long a) { long r = a-((M*(a&mask)>>>31)+M*(a>>>31)>>>h-31)*mod; return r < mod ? r : r-mod; } private static final long mask = (1L<<31)-1; public static int[] enumInvs(int n, int mod) { int[] inv = new int[n+1]; inv[1] = 1; for(int i = 2;i <= n;i++){ inv[i] = (int)modh(inv[mod%i]*(long)(mod-mod/i)); } return inv; } public static class XorShift { private long x=123456789, y=362436069, z=521288629, w=88675123; protected long next(){ long t=(x^x<<11)&(1L<<32)-1; x=y; y=z; z=w; w=(w^w>>>19^t^t>>>8)&(1L<<32)-1; return w; } } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }