結果
問題 | No.97 最大の値を求めるくえり |
ユーザー |
👑 |
提出日時 | 2025-01-28 23:48:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,095 ms / 5,000 ms |
コード長 | 1,652 bytes |
コンパイル時間 | 4,296 ms |
コンパイル使用メモリ | 307,012 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-28 23:48:35 |
合計ジャッジ時間 | 13,579 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 |
ソースコード
// https://yukicoder.me/submissions/802072// #pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include<bits/stdc++.h>#include<atcoder/modint>using namespace std;using namespace atcoder;using mint = modint;unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;unsigned xor128() {unsigned t = xor128_x ^ (xor128_x << 11);xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));}void generateA(int N, int A[]) {for(int i = 0; i < N; ++ i)A[i] = xor128() % 100003;}void solve(){mint::set_mod(100003);int n, Q;cin >> n >> Q;int A[100100];generateA(n, A);set<int> se;for(int i = 0; i < n; i++) se.insert(A[i]);bool small = true;if (se.size() >= 700){small = false;}for(int i = 0; i < Q; i++){int x;cin >> x;if(x == 0){cout << 0 << "\n";}else if(small){int ma = 0;for(auto s:se){int y = (mint(s) * x).val();if(y > ma) ma = y;}cout << ma << "\n";}else{mint mx = x;mx = mx.inv();for(int y = 100002; y > 0; y--){if(se.count((mx * y).val())){cout << y << "\n";break;}}}}}int main(){cin.tie(0)->sync_with_stdio(0);int t;t = 1;// cin >> t;while(t--) solve();}