#2595 (C++11) No.97 最大の値を求めるくえり

提出ソース

結果

問題	No.97 最大の値を求めるくえり
ユーザー	anta
提出日時	2014-11-16 17:31:35
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	99 ms / 5,000 ms
コード長	6,542 bytes
コンパイル時間	1,486 ms
コンパイル使用メモリ	91,004 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-30 07:09:50
合計ジャッジ時間	5,778 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	69 ms 4,384 KB
testcase_01	AC	23 ms 4,384 KB
testcase_02	AC	99 ms 4,384 KB
testcase_03	AC	97 ms 4,384 KB
testcase_04	AC	76 ms 4,380 KB
testcase_05	AC	76 ms 4,380 KB
testcase_06	AC	77 ms 4,384 KB
testcase_07	AC	82 ms 4,384 KB
testcase_08	AC	88 ms 4,380 KB
testcase_09	AC	93 ms 4,384 KB
testcase_10	AC	98 ms 4,380 KB
testcase_11	AC	95 ms 4,380 KB
testcase_12	AC	89 ms 4,384 KB
testcase_13	AC	81 ms 4,380 KB
testcase_14	AC	57 ms 4,380 KB
testcase_15	AC	46 ms 4,380 KB
testcase_16	AC	44 ms 4,384 KB
testcase_17	AC	44 ms 4,380 KB
testcase_18	AC	43 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

const int MaxN = 100003, MaxQ = 100003, Mod = 100003;

namespace gen {
	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() % Mod;
	}
}

int inverse(long long a, const int MOD) {
	long long b = MOD, u = 1, v = 0;
	while(b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	return (u % MOD + MOD) % MOD;
}

pii getGaps(const vector<bool> &Af) {
	pii largest(-1, -1);
	reu(i, 1, Mod) {
		int invi = inverse(i, Mod);
		for(int j = Mod-1; j >= 1; -- j) {
			int k = (long long)invi * j % Mod;
			if(Af[k]) {
				int gap = Mod - j;
				amax(largest, mp(gap, i));
				break;
			}
		}
	}
	return largest;
}

int main() {
	int N;
	while(~scanf("%d", &N)) {
		if(N == -1) {
			int strategy, parameter;
			scanf("%d%d", &strategy, &parameter);
			void gen_test(int strategy, int parameter);
			gen_test(strategy, parameter);
			return 0;
		}
		int Q;
		scanf("%d", &Q);
		if(!(1 <= N && N <= MaxN && 1 <= Q && Q <= MaxQ)) {
			cerr << "err" << endl;
			return 1;
		}
		vector<int> A(N);
		gen::generateA(N, &A[0]);
		vector<bool> Af(Mod, false);
		rep(i, N)
			Af[A[i]] = true;
		//計算量は、ギャップがB以上であるものの個数をXとしてO(N×X + B×Mod) (これは上界であって正確ではない)
		//ギャップは成功率N/Modのベルヌーイ試行の失敗回数として近似できて
		//(Mod/Nが小さい定数の時はそもそも小さい定数になって、NがModに対してある程度小さい時は重複は少ないので)、
		//B回失敗する確率は(1-N/Mod)^B。
		//足し算の左辺はBに対して単調減少、右辺は単調増加
		//Mod ~ 10^5 の場合は B ~ 200 程度で最大で4e7程度にしかならないことがわかる。
		//定数は軽い。よって、これで大丈夫。
		const int B = 200;
#if 0
		pair<pair<double,int>,int> mB(mp(1e99,-1),-1);
		for(int b = 1; b <= 1000; ++ b) {
			pair<double,int> ma(0,-1);
			for(int n = 1; n <= MaxN; n += 10) {
				double p = n * 1. / Mod;
				double X = pow(1 - p, b) * Mod;
				double a = n * X + b * Mod;
				amax(ma, mp(a, n));
			}
			amin(mB, mp(ma, b));
		}
		cerr << "mB: " << mB.first.first << ", " << mB.first.second << ", " << mB.second << endl;
#endif
		vector<int> precomputed(Mod);
		precomputed[0] = 0;
		int complexity = 0;
		for(int i = 1; i < Mod; ++ i) {
			int invi = inverse(i, Mod);
			for(int j = Mod-1, cnt = 0; j >= 1, cnt < B; -- j, ++ cnt) {
				int k = (long long)invi * j % Mod;
				++ complexity;
				if(Af[k]) {
					precomputed[i] = j;
					break;
				}
			}
			if(precomputed[i] == 0) {
				int mx = -1;
				rep(ai, N) {
					++ complexity;
					int j = (long long)i * A[ai] % Mod;
					if(mx < j)
						mx = j;
				}
				precomputed[i] = mx;
			}
		}
//		cerr << "precomputed; complexity = " << complexity << endl;
#if 1
		rep(ii, Q) {
			int q;
			scanf("%d", &q);
			if(!(0 <= q && q < Mod)) {
				cerr << "err" << endl;
				return 1;
			}
			int ans = precomputed[q];
			printf("%d\n", ans);
		}
#endif
	}
	return 0;
}

struct Xor128 {
	unsigned x, y, z, w;
	Xor128(): x(123456789), y(362436069), z(521288629), w(88675123) { }
	unsigned operator()() {
		unsigned t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
	}
	unsigned operator()(unsigned n) { return operator()() % n; }
} xor128;

int genLR(int L, int R) {
	return L + xor128() % (R - L + 1);
}

int getGap(int i, const vector<bool> &Af) {
	int invi = inverse(i, Mod);
	for(int j = Mod-1, cnt = 1; j >= 1; -- j, ++ cnt) {
		int k = (long long)invi * j % Mod;
		if(Af[k])
			return cnt;
	}
	return -1;
}

//parameter = N
void gen_test(int strategy, int parameter) {
	xor128 = Xor128();
	xor128.z = strategy, xor128.w = parameter;
	rep(ii, 100) xor128();
	int N = parameter;
	vector<int> A(N);
	gen::generateA(N, &A[0]);
	vector<bool> Af(Mod, false);
	rep(i, N) Af[A[i]] = true;
	vi queries;
	if(strategy == 0) {
		//全部
		rep(i, Mod)
			queries.push_back(i);
		random_shuffle(all(queries), [](int n) { return xor128() % n; });
	}else if(strategy == 1) {
		//gapが大きいやつだけ
		vpii gaps(Mod);
		gaps[0] = mp(0, 0);
		reu(i, 1, Mod) gaps[i] = mp(getGap(i, Af), i);
		sort(all(gaps), greater<pii>());
		rep(i, MaxQ)
			queries.push_back(gaps[i % 100].second);
		random_shuffle(all(queries), [](int n) { return xor128() % n; });
	}else if(strategy == 2) {
		//完全ランダム
		rep(i, MaxQ)
			queries.push_back(genLR(0, Mod-1));
	}else if(strategy == 3) {
		//完全ランダム small
		rep(i, 100)
			queries.push_back(genLR(0, Mod-1));
	}
	printf("%d %d\n", N, (int)queries.size());
	each(i, queries)
		printf("%d\n", *i);
}

yukicoder

結果

テストケース

ソースコード