#1082163 (C++17) No.3120 Lower Nim

• 問題: No.3120 Lower Nim
• ユーザー: ROBORU
• 提出日時: 2025-05-04 05:24:01
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 237 ms / 2,000 ms
• コード長: 13,491 bytes
• コンパイル時間: 1,605 ms
• コンパイル使用メモリ: 128,472 KB
• 実行使用メモリ: 26,228 KB
• 平均クエリ数: 2685.91
• 最終ジャッジ日時: 2025-05-04 05:24:11
• 合計ジャッジ時間: 10,148 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 43

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cfloat>
#include <climits>
#include <cmath>
#include <numeric>
#include <functional>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;


/// <summary>
/// どれがいくつ入ってるかを高速(?)にソートする。
/// </summary>
/// <typeparam name="T"></typeparam>
template<typename T>
class MultiNum {
	map<T, ll> elementToIdMap;
	map<ll, T> idToElementMap;
	vector<pair<ll, ll>> elementNum;
	vector<pair<ll, ll>> sorted;

public:

	void Add(T element) {
		if (elementToIdMap.count(element) <= 0) {
			elementNum.push_back(pair<ll, ll>(0, elementToIdMap.size()));
			idToElementMap[elementToIdMap.size()] = element;
			elementToIdMap[element] = elementToIdMap.size();
		}
		elementNum[elementToIdMap[element]].first++;
	}

	void SortLess() {
		sorted = elementNum;
		sort(sorted.begin(), sorted.end());
	}
	void SortGreater() {
		sorted = elementNum;
		sort(sorted.begin(), sorted.end(), greater<pair<ll, ll>>());
	}

	vector<pair<T, ll>> GetResult() {
		vector<pair<T, ll>> result;
		for (ll i = 0; i < sorted.size(); i++) {
			result.push_back(pair<T, ll>(idToElementMap[sorted[i].second], sorted[i].first));
		}

		return result;
	}
};

class nCk {
	const ll divs;
	const ll maxSize;
	vector<ll> fac;
	vector<ll> invFac;


	ll divsPow(ll base, ll exponent) {
		ll answer = 1;

		while (0 < exponent) {
			if (exponent & 1) {
				answer = (answer * base) % divs;
				exponent--;
				continue;
			}

			base = (base * base) % divs;
			exponent = exponent >> 1;
		}

		return answer;
	}

public:
	nCk(ll _divs, ll _max) : divs(_divs), maxSize(_max) {
		//index0,1は全て1と考えられる。
		fac.push_back(1);
		fac.push_back(1);
		invFac.push_back(1);
		invFac.push_back(1);

		for (ll i = 2; i <= maxSize; i++) {
			fac.push_back((fac[i - 1] * i) % divs);
			invFac.push_back((invFac[i - 1] * divsPow(i, divs - 2)) % divs);
		}
	}

	ll Execute(ll n, ll k) {
		if (n < k) return 0;
		if (n < 0 || k < 0) return 0;
		return (fac[n] * ((invFac[k] * invFac[n - k]) % divs)) % divs;
	}
};


template<typename Ty>
class IdMap {

	set<Ty> _isExist;
	map<Ty, ll> _map;
	function<void(Ty)> _newIdAction;


public:
	IdMap(function<void(Ty)> newIdAction) {
		_newIdAction = newIdAction;
	}

	ll getId(Ty id) {
		if (_isExist.count(id) <= 0) {
			_isExist.insert(id);
			_map[id] = _map.size();
			_newIdAction(id);
		}
		return _map[id];
	}
};




class UnionFind {
private:
	vector<int> parent;

public:
	UnionFind(int size) : parent(size, -1) {
		//		iota(parent.begin(), parent.end(), -1);
	}


	int FindRoot(int v) {
		// -1ならrootは自分になる。
		if (parent[v] < 0) return v;
		// root更新していく
		parent[v] = FindRoot(parent[v]);
		return parent[v];
	}

	void Unite(int a, int b) {
		int rootA = FindRoot(a);
		int rootB = FindRoot(b);
		// rootが同じなら何もしない。
		if (rootA == rootB) return;
		parent[rootB] = rootA;
	}

	bool IsSameRoot(int a, int b) {
		if (FindRoot(a) == FindRoot(b)) return true;
		else return false;
	}

};

template<typename T>
class SegmentTree {
	vector<T> e;
	size_t size;
	function<T(T, T)> calc;
	const T identity;

	size_t get_new_size(size_t prevSize) {
		size_t newSize = 1;
		for (; newSize < prevSize; newSize *= 2) {}
		return newSize;
	}

	size_t get_eId(size_t id) {
		return id + size;
	}

	void updateFromChildren(size_t eId) {
		if (eId == 0) return;
		e[eId] = calc(e[eId * 2], e[eId * 2 + 1]);
		updateFromChildren(eId / 2);
	}

	T getRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed) {
		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return identity;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			return e[eId];
		}

		// まだ絞り切れてない
		return
			calc(
				getRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed),
				getRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed)
			);
	}

public:
	SegmentTree(size_t _size, T initNum, function<T(T, T)> _calc) :
		size(get_new_size(_size)),
		identity(initNum),
		calc(_calc)
	{
		e.resize(2 * size, identity);
	}

	void update(size_t id, T newValue) {
		auto elementId = get_eId(id);
		e[elementId] = newValue;
		updateFromChildren(elementId / 2);
	}

	T getOne(size_t id) {
		return e[get_eId(id)];
	}

	/// <summary>
	/// [leftId, rightId)
	/// </summary>
	T getRange(size_t leftId, size_t rightId) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return getRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId);
	}
};

template<typename T>
class LazySegmentTree {
	vector<T> e;
	vector<T> lazyE;
	vector<bool> hasLazyValue;
	size_t size;
	function<T(T, T)> calc;
	function<T(T, T)> operateByLazy;
	const T identity;

	size_t get_new_size(size_t prevSize) {
		size_t newSize = 1;
		for (; newSize < prevSize; newSize *= 2) {}
		return newSize;
	}

	size_t get_eId(size_t id) {
		return id + size;
	}

	void updateRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed, T newValue) {
		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			e[eId] = operateByLazy(e[eId], newValue);
			if (eId < size) {
				lazyE[eId * 2] = newValue;
				lazyE[eId * 2 + 1] = newValue;
				hasLazyValue[eId * 2] = true;
				hasLazyValue[eId * 2 + 1] = true;
			}
			return;
		}

		// まだ絞り切れてない
		updateRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed, newValue);
		updateRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed, newValue);
		// 子のupdateに応じて親をupdateさせる
		e[eId] = calc(e[eId * 2], e[eId * 2 + 1]);
	}

	T getRange(size_t eId, size_t lIdFromEId, size_t rIdFromEId, size_t lIdNeed, size_t rIdNeed) {
		//lazy評価
		if (hasLazyValue[eId]) {
			e[eId] = operateByLazy(e[eId], lazyE[eId]);
			hasLazyValue[eId] = false;
			// 子がいるなら子にも伝搬する
			if (eId < size) {
				lazyE[eId * 2] = lazyE[eId];
				lazyE[eId * 2 + 1] = lazyE[eId];
				hasLazyValue[eId * 2] = true;
				hasLazyValue[eId * 2 + 1] = true;
			}
		}

		// 完全に範囲外にでた
		if (rIdNeed <= lIdFromEId || rIdFromEId <= lIdNeed) {
			return identity;
		}

		// 完全に囲まれた
		if (lIdNeed <= lIdFromEId && rIdFromEId <= rIdNeed) {
			return e[eId];
		}

		// まだ絞り切れてない
		e[eId] = calc(
			getRange(eId * 2, lIdFromEId, (rIdFromEId + lIdFromEId) / 2, lIdNeed, rIdNeed),
			getRange(eId * 2 + 1, (rIdFromEId + lIdFromEId) / 2, rIdFromEId, lIdNeed, rIdNeed)
		);
		return e[eId];
	}

public:
	LazySegmentTree(size_t _size, T initNum, function<T(T, T)> _calc, function<T(T, T)> _operateByLazy) :
		size(get_new_size(_size)),
		identity(initNum),
		calc(_calc),
		operateByLazy(_operateByLazy)
	{
		e.resize(2 * size, identity);
		lazyE.resize(2 * size, identity);
		hasLazyValue.resize(2 * size, false);
	}

	void updateRange(size_t leftId, size_t rightId, T newValue) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return updateRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId, newValue);
	}

	void update(size_t id, T newValue) {
		updateRange(id, id + 1, newValue);
	}

	/// <summary>
	/// [leftId, rightId)
	/// </summary>
	T getRange(size_t leftId, size_t rightId) {
		size_t start_eId = 1;
		size_t lIdFromEId = 0, rIdFromEId = size;
		return getRange(start_eId, lIdFromEId, rIdFromEId, leftId, rightId);
	}

	T getOne(size_t id) {
		return getRange(id, id + 1);
	}
};

class scc {
	ll n;
	vector<vector<ll>> groups;

	void searchMe(ll id, ll& nowScore, vector<ll>& score, vector<vector<ll>>& edge) {
		if (0 <= score[id]) return;
		score[id] = 0;

		for (auto& p : edge[id]) {
			searchMe(p, nowScore, score, edge);
		}
		score[id] = nowScore++;
	}

	void reverseSearchMe(ll id, vector<ll>& cameIds, vector<bool>& hasCame, vector<vector<ll>>& edge) {
		if (hasCame[id]) return;
		hasCame[id] = true;
		cameIds.push_back(id);
		for (auto& p : edge[id]) {
			reverseSearchMe(p, cameIds, hasCame, edge);
		}
	}

public:
	scc(ll _n, vector<pair<ll, ll>> _edge) : n(_n) {
		vector<vector<ll>> edge(n), backE(n);
		for (auto& e : _edge) {
			edge[e.first].push_back(e.second);
			backE[e.second].push_back(e.first);
		}

		vector<ll> score(n, -1);
		ll nowScore = 0;
		for (ll i = 0; i < n; i++) {
			searchMe(i, nowScore, score, edge);
		}

		vector<ll> idScore(n, -1);
		for (ll i = 0; i < n; i++) {
			idScore[score[i]] = i;
		}

		vector<bool> hasCame(n, false);
		for (ll i = n - 1; 0 <= i; i--) {
			vector<ll> cameIds;
			reverseSearchMe(idScore[i], cameIds, hasCame, backE);
			groups.push_back(cameIds);
		}
	}

	vector<vector<ll>>& getGroups() {
		return groups;
	}
};

template<typename T>
class queueVec {
	ll sItr, eItr;
	vector<T> vec;
public:
	queueVec(ll capacity) {
		sItr = 0;
		eItr = 0;
		vec.reserve(capacity);
	}

	ll size() {
		return eItr - sItr;
	}

	void push(T value) {
		eItr++;
		vec.emplace_back(value);
	}

	void pop() {
		sItr++;
	}

	T front() {
		return vec[sItr];
	}
};

class Lca {
	vector<vector<ll>> parents;
	vector<vector<ll>> es;
	vector<ll> depths;
	ll maxDepthLog2;

public:
	Lca(ll n, vector<pair<ll, ll>>& edges) {
		ll kaisou = log2l(n - 1) + 1;
		parents = vector<vector<ll>>(n, vector<ll>(kaisou, -1));
		depths = vector<ll>(n);

		// make tree
		{
			es = vector<vector<ll>>(n);
			for (auto& e : edges) {
				es[e.first].push_back(e.second);
				es[e.second].push_back(e.first);
			}

			parents[0][0] = 0;
			queueVec<ll> queueP(n);
			queueP.push(0);
			ll d = 0;
			for (d = 0; 0 < queueP.size(); d++) {
				ll qNum = queueP.size();
				for (ll q = 0; q < qNum; q++) {
					auto p = queueP.front();
					queueP.pop();
					depths[p] = d;

					for (auto& np : es[p]) {
						if (parents[np][0] < 0) {
							parents[np][0] = p;
							queueP.push(np);
						}
					}
				}
			}
			maxDepthLog2 = (ll)log2l(d - 1) + 1;

			for (ll k = 1; k < kaisou; k++) {
				for (ll i = 0; i < n; i++) {
					parents[i][k] = parents[parents[i][k - 1]][k - 1];
				}
			}
		}
	}

	ll getAncestor(ll v, ll steps) {
		for (ll k = 0, k2 = 1; k2 <= steps; k++, k2 *= 2) {
			if (0 < (k2 & steps)) {
				v = parents[v][k];
			}
		}
		return v;
	}

	ll commonAncestor(ll a, ll b) {
		if (depths[a] < depths[b]) {
			b = getAncestor(b, depths[b] - depths[a]);
		}
		else if (depths[b] < depths[a]) {
			a = getAncestor(a, depths[a] - depths[b]);
		}

		if (a == b) return a;
		for (ll k = maxDepthLog2; 0 <= k; k--) {
			if (parents[a][k] == parents[b][k]) continue;
			a = parents[a][k];
			b = parents[b][k];
		}

		return parents[a][0];
	}

	ll distance(ll a, ll b) {
		return depths[a] + depths[b] - 2 * depths[commonAncestor(a, b)];
	}

	pair<ll, ll> diameterVs() {
		ll v;
		ll maxD = -1;
		for (ll i = 0; i < depths.size(); i++) {
			if (maxD < depths[i]) {
				maxD = depths[i];
				v = i;
			}
		}

		pair<ll, ll> answer = { v, v };
		ll farV = -1;
		queueVec<ll> nextP(depths.size());
		vector<bool> isReached(depths.size(), false);
		nextP.push(v);
		isReached[v] = true;
		while (0 < nextP.size()) {
			ll qSize = nextP.size();
			for (ll q = 0; q < qSize; q++) {
				auto p = nextP.front();
				nextP.pop();
				farV = p;
				for (auto& np : es[p]) {
					if (isReached[np]) continue;
					isReached[np] = true;
					nextP.push(np);
				}
			}
		}
		answer.second = farV;
		return answer;
	}
};

const string myFirst = "First";
const string mySecond = "Second";
ll n;
vector<ll> a;

ll calculateWhatNumberToWin() {
	ll maxA = 0; for (auto& ai : a) maxA = max(maxA, ai);
	for (ll startk = 1; startk <= maxA; startk <<= 1) {
		ll tekazuNum = 0;
		ll amariNum = 0;
		for (auto& ai : a) {
			tekazuNum += ai / startk;
			if (0 < ai % startk) amariNum++;
		}
		if (tekazuNum % 2 == 1) {
			return startk;
		}
	}
	return -1;
}

void canWinByFirst(ll startk) {
	ll k = startk;
	bool nowPlaying = true;
	set<ll> nokoriyama;
	for (ll i = 0; i < n; i++) {
		if(k <= a[i]) nokoriyama.insert(i);
	}
	while (true) {
		if (nokoriyama.size() == 0) {
			k = calculateWhatNumberToWin();
			if (k < 0) {
				cout << a[1000000] << endl;
				cout << "Arienai" << endl;
				return;
			}
			canWinByFirst(k);
			return;
		}
		ll sousaYama = *nokoriyama.begin();
		cout << sousaYama + 1 << " " << k << endl;
		a[sousaYama] -= k;
		if (a[sousaYama] < k) nokoriyama.erase(sousaYama);
		ll ret;
		cin >> ret;
		if (ret == 1) return;

		ll ji, xi;
		cin >> ji >> xi;
		ji--;
		a[ji] -= xi;
		cin >> ret;
		if (k != xi) {
			k = calculateWhatNumberToWin();
			if(k < 0 || xi < k) {
				cout << a[1000000] << endl;
				cout << "Arienai" << endl;
				return;
			}
			canWinByFirst(k);
			return;
		}
		if (a[ji] < k) nokoriyama.erase(ji);
	}
}

int main()
{
	cin >> n;

	a = vector<ll>(n);
	for (ll i = 0; i < n; i++) cin >> a[i];

	ll k = calculateWhatNumberToWin();
	if (0 < k) {
		cout << myFirst << endl;
		canWinByFirst(k);
	}
	else {
		cout << mySecond << endl;
		ll i, x;
		cin >> i >> x;
		i--;
		a[i] -= x;
		ll ret;
		cin >> ret;

		ll k = calculateWhatNumberToWin();
		if (0 < k) {
			canWinByFirst(k);
		}
		else {
			cout << a[1000000] << endl;
			cout << "Arienai" << endl;
		}
	}
}