結果

問題 No.97 最大の値を求めるくえり
ユーザー 37zigen37zigen
提出日時 2020-08-30 23:45:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 378 ms / 5,000 ms
コード長 1,507 bytes
コンパイル時間 692 ms
コンパイル使用メモリ 75,596 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-27 13:44:00
合計ジャッジ時間 6,875 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
6,816 KB
testcase_01 AC 18 ms
6,940 KB
testcase_02 AC 284 ms
6,944 KB
testcase_03 AC 279 ms
6,944 KB
testcase_04 AC 179 ms
6,940 KB
testcase_05 AC 185 ms
6,944 KB
testcase_06 AC 191 ms
6,940 KB
testcase_07 AC 203 ms
6,944 KB
testcase_08 AC 209 ms
6,940 KB
testcase_09 AC 227 ms
6,940 KB
testcase_10 AC 271 ms
6,940 KB
testcase_11 AC 305 ms
6,944 KB
testcase_12 AC 340 ms
6,940 KB
testcase_13 AC 378 ms
6,940 KB
testcase_14 AC 200 ms
6,940 KB
testcase_15 AC 195 ms
6,944 KB
testcase_16 AC 195 ms
6,944 KB
testcase_17 AC 195 ms
6,944 KB
testcase_18 AC 187 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main() {
      | ^~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

const long long MOD=100003;
long long ind[MOD];

long long pow_mod(long long a,long long n) {
    return n!=0?pow_mod(a*a%MOD,n/2)*(n%2==1?a:1)%MOD:1;
}

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));
}

vector<int> generateA(int N) {
  vector<int> A(N);
  for(int i = 0; i < N; ++ i)
    A[i] = xor128() % MOD;
  return A;
}

main() {
    int g=2;
    for (int i=0;i<MOD;++i) {
        ind[pow_mod(g,i)]=i;
    }
    
    int N,Q;
    cin>>N>>Q;
    bool ok[MOD];
    auto A=generateA(N);
    int sz=0;
    for (int i=0;i<MOD;++i) ok[i]=false;
    for (long long v:A) {
        if (v!=0) {
            ok[ind[v]]=true;
            ++sz;
        }
    }
    while (Q--) {
        int q;
        cin>>q;
        if (q==0) {
            cout<<0<<endl;
            continue;
        }
        int ind_q=ind[q];
        int ans=0;
        int ord=MOD-1;
        if (N>1000) {
            for (int i=MOD-1;i>=1;--i) {
                if (ok[(ind[i]-ind_q+ord)%ord]) {
                    ans=i;
                    break;
                }
            }
        } else {
            for (long long v:A) {
                ans=max(ans,(int)(v*q%MOD));
            }
        }
        cout<<ans<<endl;
    }
    
}
0