結果
問題 | No.250 atetubouのzetubou |
ユーザー |
![]() |
提出日時 | 2015-07-25 01:54:43 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 23,966 bytes |
コンパイル時間 | 1,018 ms |
コンパイル使用メモリ | 112,172 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-16 04:26:03 |
合計ジャッジ時間 | 2,375 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream>#include <array>#include <vector>#include <list>#include <stack>#include <queue>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <algorithm>#include <string>#include <sstream>#include <memory>#include <cassert>#include <functional>#define SAFE_DELETE(p) { delete (p); (p) = nullptr; }#define SAFE_DELETE_ARRAY(p) { delete[] (p); (p) = nullptr; }using namespace std;namespace ValLib {const int MOD = 1000000007;typedef unsigned long long ull;template <typename Key, typename Value>class unordered_vmap;template <typename T>using sptr = typename std::shared_ptr<T>;class vnode;class vegde;class vgraph;class SearchResult;template<typename T>void fill(vector<vector<T>>& vec, const T& value) {for (vector<T>& t : vec) {fill(t, value);}}template<typename T>void fill(vector<T>& vec, const T& value) {fill(vec.begin(), vec.end(), value);}template<typename T>void resize(vector<vector<T>>& vec, int size1, int size2) {vec.resize(size1);for (vector<T>& t : vec) {t.resize(size2);}}template<typename Key, typename Value>class umap : public std::unordered_map<Key, Value> {public:bool containsKey(const Key& key) const;bool containsValue(const Value& val) const;};template<typename Key, typename Value>bool umap<Key, Value>::containsKey(const Key& key) const {return (this->find(key) != this->end());}template<typename Key, typename Value>bool umap<Key, Value>::containsValue(const Value& val) const {for(auto itr = this->begin(); itr != this->end(); ++itr) {if (itr->second == val) {return true;}}return false;}class Point {public:inline Point() :x(-1),y(-1){}inline Point(int _x, int _y) :x(_x),y(_y){}int x;int y;};/// <summary>/// 素集合データ構造/// </summary>class UnionFind {public:/// <summary>/// コンストラクタ/// </summary>/// <param name="N">要素数</param>UnionFind(int N) {parent.resize(N);for (int i = 0; i < N; ++i) {parent[i] = i;}}/// <summary>/// 要素xの根を探索/// </summary>/// <param name="x">探索する要素番号(0~N-1)</param>/// <returns>要素xの根(0~N-1)</returns>int find(int x) {if (parent[x] == x) {return x;} else {parent[x] = find(parent[x]); // 経路圧縮(間接的な要素をrootに直接つなぐ)return parent[x];}}/// <summary>/// 2つの要素の根が同じか/// </summary>/// <param name="x1">探索する要素番号1(0~N-1)</param>/// <param name="x2">探索する要素番号2(0~N-1)</param>/// <returns>true: 同じ根, false: 異なる根</returns>bool same(int x1, int x2) {return find(x1) == find(x2);}/// <summary>/// 2つの要素の根同士を繋ぐ/// </summary>/// <param name="x1">要素番号1(0~N-1)</param>/// <param name="x2">要素番号1(0~N-1)</param>void union_elements(int x1, int x2) {int rootX1 = find(x1);int rootX2 = find(x2);parent[rootX2] = rootX1;}private:vector<int> parent;};class vmath {public:// 約数を全て求める O(√n)static ull calcDivisors(list<ull>* divisors, ull n) {divisors->clear();if (n <= 0ull) {return 0ull;}divisors->push_back(1ull);if (n != 1ull) {divisors->push_back(n);}for (ull i = 2ull; i * i <= n; ++i) {if (n % i == 0ull) {divisors->push_back(i);divisors->push_back(n / i);}}return divisors->size();}// 約数の個数を返す O(√n)static ull calcDivisorNum(ull n) {if (n <= 0ull) {return 0ull;}ull count = 1ull; // for 1if (n != 1ull) {++count; // for n}// for 2~n-1for (ull i = 2ull; i * i <= n; ++i) {if (n % i == 0ull) {count += 2ull;}}return count;}// 素因数分解 O(√n)static int decompositPrime(list<ull>* primes, ull n) {primes->clear();if (n == 0) {return 0ull;}if (n == 1) {primes->push_back(1);return 1ull;}// 割る数の初期値ull a = 2ull;// √n ≧ a ( n ≧ a * a ) の間ループ処理while (n >= a * a) {if (n % a == 0ull) {// a で割り切れたら、a は素因数primes->push_back(a);// そして、割られる数を a で割るn /= a;} else {// a で割り切れなかったら、 a を 1 増加させるa++;}}primes->push_back(n);return primes->size();}// 素因数の数を返す O(√n)static ull calcPrimeNum(ull n) {if (n <= 1) {return n;}ull count = 0ull;// 割る数の初期値ull a = 2ull;// √n ≧ a ( n ≧ a * a ) の間ループ処理while (n >= a * a) {if (n % a == 0ull) {// a で割り切れたら、a は素因数++count;// そして、割られる数を a で割るn /= a;} else {// a で割り切れなかったら、 a を 1 増加させるa++;}}++count; // for nreturn count;}// 階乗static ull fact(ull x) {if (x == 0ull) {return 1ull;} else {return x * fact(x - 1ull);}}// 順列 nPrstatic ull permutation(int n, int r) {assert(n >= r);//return fact(n) / fact(n - r);ull result = 1;for (ull i = n; i > n - r; --i) {result *= i;}return result;}// 組み合わせ nCr// 先にmakePascalTriangleでパスカルの三角形を作成しておく必要があるstatic ull combination(int n, int r) {assert(n >= r);assert(n <= mPascalTriangleDepth);return mPascalTriangle[n][r];}// 重複組合せ nHr = n+r-1Cr// 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか// 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。// これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1// (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Crstatic ull repeatedCombination(int n, int r) {return combination(n + r - 1, r);}// パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。static void makePascalTriangle(int depth) {resize(mPascalTriangle, depth + 1, depth + 1);for (int i = 0; i <= depth; ++i) {mPascalTriangle[i][0] = 1;for (int j = 1; j <= i; ++j) {mPascalTriangle[i][j] = mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1];}}mPascalTriangleDepth = depth;}// xのN桁目の数値を得るstatic ull getNDigitNumber(ull x, ull n) {return (x / pow(10ull, n - 1ull)) % 10;}// xのN桁目の数値を得るstatic int getNDigitNumber(int x, int n) {assert(n <= 10);return (x / pow(10, n - 1)) % 10;}// xのN乗を求める(バイナリ法) O(logN)static ull pow(ull x, ull n) {assert(x >= 0ull);assert(n >= 0ull);if (x == 0ull) {if (n == 0ull) {return 1ull;} else {return 0ull;}}ull result = 1ull;ull z = x;while (n > 0ull) {if (n & 1ull) {result *= z;}z *= z;n >>= 1;}return result;}// xのN乗を求める(バイナリ法) O(logN)static int pow(int x, int n) {assert(x >= 0);assert(n >= 0);if (x == 0) {if (n == 0) {return 1;} else {return 0;}}int result = 1;int z = x;while (n > 0) {if (n & 1) {result *= z;}z *= z;n >>= 1;}return result;}private:static int mPascalTriangleDepth;static vector<vector<ull>> mPascalTriangle;};int vmath::mPascalTriangleDepth = 0;vector<vector<ull>> vmath::mPascalTriangle;class vmath_mod {public:// 階乗static ull fact(ull x) {ull result = 1ull;for (ull i = 1ull; i <= x; ++i) {result *= i;result %= MOD;}return result;}// 順列 nPrstatic ull permutation(int n, int r) {assert(n >= r);//return fact(n) / fact(n - r);ull result = 1;for (ull i = n; i > n - r; --i) {result *= i;result %= MOD;}return result;}// 組み合わせ nCr// 先にmakePascalTriangleでパスカルの三角形を作成しておく必要があるstatic ull combination(int n, int r) {assert(n >= r);assert(n <= mPascalTriangleDepth);return mPascalTriangle[n][r];}// 重複組合せ nHr = n+r-1Cr// 使いどころ:n人にr個を配るとき、同じ人に何個配っても良い場合とか// 4人に5個の◯を配るときa=2,b=0,c=2,d=1のとき、◯◯||◯◯|◯みたいになる。// これは◯と|を混ぜた組み合わせで、◯の数がn,棒の数はr-1だから全体でn+r-1// (n-r)で割ったものが順列n+r-1Prで、それを更にrで割っているからnHr = n+r-1Crstatic ull repeatedCombination(int n, int r) {return combination(n + r - 1, r);}// パスカルの三角形。組み合わせの計算に使用するのでこれを先に作成しておく必要がある。static void makePascalTriangle(int depth) {resize(mPascalTriangle, depth + 1, depth + 1);for (int i = 0; i <= depth; ++i) {mPascalTriangle[i][0] = 1;for (int j = 1; j <= i; ++j) {mPascalTriangle[i][j] = (mPascalTriangle[i - 1][j] + mPascalTriangle[i - 1][j - 1]) % MOD;}}mPascalTriangleDepth = depth;}// xのN桁目の数値を得るstatic ull getNDigitNumber(ull x, ull n) {return (x / pow(10ull, n - 1ull)) % 10;}// xのN桁目の数値を得るstatic int getNDigitNumber(int x, int n) {assert(n <= 10);return (x / pow(10, n - 1)) % 10;}// xのN乗を求める O(n)static ull pow(ull x, ull n) {if (x == 0ull) {if (n == 0ull) {return 1ull;} else {return 0ull;}}ull result = 1ull;for (ull i = 0ull; i < n; ++i) {result *= x;result %= MOD;}return result;}// xのN乗を求める O(n)static int pow(int x, int n) {assert(x >= 0);assert(n >= 0);if (x == 0) {if (n == 0) {return 1;} else {return 0;}}int result = 1;for (int i = 0; i < n; ++i) {result *= x;result %= MOD;}return result;}private:static int mPascalTriangleDepth;static vector<vector<ull>> mPascalTriangle;};int vmath_mod::mPascalTriangleDepth = 0;vector<vector<ull>> vmath_mod::mPascalTriangle;class vegde {public:vegde() :mLeft(nullptr),mRight(nullptr) {}vegde(sptr<vnode> left, sptr<vnode> right) :vegde() {mLeft = left;mRight = right;}vegde(sptr<vnode> left, sptr<vnode> right, int cost) :vegde(left, right) {mCost = cost;}sptr<vnode> getOpponent(sptr<vnode> node) const {assert(node == mLeft || node == mRight);return (node == mLeft) ? mLeft : (node == mRight) ? mRight : nullptr;}void set(sptr<vnode> left, sptr<vnode> right) { mLeft = left; mRight = right; }const sptr<vnode>& getLeft() const { return mLeft; }const sptr<vnode>& getRight() const { return mRight; }int getCost() const { return mCost; }private:sptr<vnode> mLeft;sptr<vnode> mRight;int mCost;};class vnode {public:vnode() :mID(-1) {}vnode(int id) :vnode() {mID = id;}void addEgde(sptr<vegde> egde) {mEgdeList.push_back(egde);}void removeEgde(int nodeID1, int nodeID2) {auto itrNewEnd = std::remove_if(mEgdeList.begin(), mEgdeList.end(), [=](sptr<vegde> e)->bool {return (e->getLeft()->getID() == nodeID1 && e->getRight()->getID() == nodeID2);});mEgdeList.erase(itrNewEnd, mEgdeList.end());}int getID() const { return mID; }const list<sptr<vegde>>& getEgde() const { return mEgdeList; }private:list<sptr<vegde>> mEgdeList;int mID;};class AdjacencyMatrix {public:AdjacencyMatrix() {}AdjacencyMatrix(int nodeNum) {resize(mConnectionMap, nodeNum, nodeNum);resize(mCostMap, nodeNum, nodeNum);resize(mMinimumDistMap, nodeNum, nodeNum);resize(mPrevNodeMap, nodeNum, nodeNum);}void addEgde(int nodeID1, int nodeID2, int cost) {mConnectionMap[nodeID1][nodeID2] = true;mConnectionMap[nodeID2][nodeID1] = true;mCostMap[nodeID1][nodeID2] = cost;mCostMap[nodeID2][nodeID1] = cost;}void removeEgde(int nodeID1, int nodeID2) {mConnectionMap[nodeID1][nodeID2] = false;mConnectionMap[nodeID2][nodeID1] = false;mCostMap[nodeID1][nodeID2] = 0;mCostMap[nodeID2][nodeID1] = 0;}void warshallFloyd(int nodeNum) {for (int k = 0; k < nodeNum; ++k) {for (int i = 0; i < nodeNum; ++i) {for (int j = 0; j < nodeNum; ++j) {if (mConnectionMap[i][j]) {mMinimumDistMap[i][j] = mCostMap[i][j];} else {mMinimumDistMap[i][j] = 99999999;}}}}for (int k = 0; k < nodeNum; ++k) {for (int i = 0; i < nodeNum; ++i) {for (int j = 0; j < nodeNum; ++j) {mMinimumDistMap[i][j] = min(mMinimumDistMap[i][j], mMinimumDistMap[i][k] + mMinimumDistMap[k][j]);}}}//for (int i = 0; i < mNodeNum; ++i) {// for (int j = 0; j < mNodeNum; ++j) {// cerr << mMinimumDistMap[i][j] << ", ";// }// cerr << endl;//}}const vector<vector<bool>>& getConnectionMap() const { return mConnectionMap; }const vector<vector<int>>& getCostMap() const { return mCostMap; }const vector<vector<int>>& getMinimumDistMap() const { return mMinimumDistMap; }const vector<vector<int>>& getPrevNodeMap() const { return mPrevNodeMap; }private:vector<vector<bool>> mConnectionMap;vector<vector<int>> mCostMap;vector<vector<int>> mMinimumDistMap;vector<vector<int>> mPrevNodeMap;};// グラフclass vgraph {public:const int INF = 1000000;vgraph(int nodeNum) {mNodeNum = nodeNum;mNodes.resize(nodeNum);for (int i = 0; i < nodeNum; ++i) {mNodes[i] = make_shared<vnode>(i);}mMinimumDists.resize(mNodeNum);mPrevNodes.resize(mNodeNum);}void addEgde(int nodeID1, int nodeID2) {addEgde(nodeID1, nodeID2, 1);}virtual void addEgde(int nodeID1, int nodeID2, int cost) = 0;virtual void removeEgde(int nodeID1, int nodeID2) = 0;// ベルマンフォード法を使ってある頂点から全ての頂点への最短距離を求める// startからたどり着ける場所に負のループが存在する場合はfalseを返す// ダイクストラ法と違い、負のコストの辺があっても最短距離を計算できる// O(V*E)bool bellmanFord(int start) {vector<int>& dist = mMinimumDists;fill(dist, INF);dist[start] = 0;for (int i = 0; i < mNodeNum; ++i) {bool update = false;for (sptr<vnode> node : mNodes) {for (sptr<vegde> egde : node->getEgde()) {int from = egde->getLeft()->getID();int to = egde->getRight()->getID();if (dist[from] == INF) {continue;}if (dist[node->getID()] + egde->getCost() < dist[to]) {dist[to] = dist[node->getID()] + egde->getCost();update = true;if (i == mNodeNum - 1) {//return false;}}}}if (!update) {break;}}return true;}// ダイクストラ法を使ってある頂点から全ての頂点への最短距離を求める// 負のコストの辺があると最短距離を計算できない点に注意する// O(E*logV)void dijkstraSearch(int start) {// Minimum distances for each nodesvector<int>& dpMinDists = mMinimumDists;fill(dpMinDists, INF);// Result of the previous visited nodevector<int>& resultPrev = mPrevNodes;fill(resultPrev, -1);// Create a priority_queue for search.typedef pair<int, int> P; // key: その頂点までの最短距離, value: 頂点の番号priority_queue<P, vector<P>, greater<P>> pq_node;// Mark the current node as visited and enqueue itpq_node.push(P(0, start));dpMinDists[start] = 0;while (!pq_node.empty()) {P p = pq_node.top();pq_node.pop();int nowDist = p.first;int nowNodeID = p.second;if (dpMinDists[nowNodeID] < nowDist) {continue;}for (sptr<vegde> egde : mNodes[nowNodeID]->getEgde()) {sptr<vnode> nextNode = egde->getRight();int nextNodeID = nextNode->getID();int nextNodeDist = nowDist + egde->getCost();if (nextNodeDist < dpMinDists[nextNodeID]) {dpMinDists[nextNodeID] = nextNodeDist;resultPrev[nextNodeID] = nowNodeID;pq_node.push(P(nextNodeDist, nextNodeID));}}}}int calcMaxDepth() const {pair<int, int> farestNodeData = getFarestNodeID(0);pair<int, int> farestNodeData2 = getFarestNodeID(farestNodeData.first);return farestNodeData2.second;}int getNodeNum() const { return mNodeNum; }const vector<int>& getMinimumDists() const { return mMinimumDists; }const vector<int>& getPrevNodes() const { return mPrevNodes; }protected:// 引数で受け取ったノードから最も遠いノードのidと距離を返す// グラフにループがあると無限ループになるので注意する(つまり木専用)pair<int, int> getFarestNodeID(int start) const {queue<pair<int, int>> q; // nodeID, このノードまでの距離q.push(make_pair(start, 0));pair<int, int> finalNodeData;vector<bool> opened(mNodeNum);fill(opened, false);while (!q.empty()) {pair<int, int> nodeData = q.front();int nodeID = nodeData.first;int dist = nodeData.second;if (dist > finalNodeData.second) {finalNodeData.second = dist;finalNodeData.first = nodeID;}q.pop();for (sptr<vegde> egde : mNodes[nodeID]->getEgde()) {int id = egde->getRight()->getID();if (opened[id]) {continue;}opened[id] = true;q.push(make_pair(id, dist + egde->getCost()));}}return finalNodeData;}int mNodeNum;bool mUseMaps;vector<sptr<vnode>> mNodes;vector<int> mMinimumDists;vector<int> mPrevNodes;};// 無向グラフ UnDirected Val Graph.class udvgraph : public vgraph {public:udvgraph(int nodeNum) :vgraph(nodeNum) {}void addEgde(int nodeID1, int nodeID2, int cost) {mNodes[nodeID1]->addEgde(make_shared<vegde>(mNodes[nodeID1], mNodes[nodeID2], cost));mNodes[nodeID2]->addEgde(make_shared<vegde>(mNodes[nodeID2], mNodes[nodeID1], cost));}void removeEgde(int nodeID1, int nodeID2) {mNodes[nodeID1]->removeEgde(nodeID1, nodeID2);mNodes[nodeID2]->removeEgde(nodeID2, nodeID1);}};// 隣接行列付きの無向グラフ。ワーシャルフロイドが使える。 UnDirected Val Graph Matrixclass udvgraph_m : public udvgraph {public:udvgraph_m(int nodeNum) :udvgraph(nodeNum) {mAdjacencyMatrix = AdjacencyMatrix(nodeNum);}void addEgde(int nodeID1, int nodeID2, int cost) {udvgraph::addEgde(nodeID1, nodeID2, cost);mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost);}void removeEgde(int nodeID1, int nodeID2) {udvgraph::removeEgde(nodeID1, nodeID2);mAdjacencyMatrix.removeEgde(nodeID1, nodeID2);}void warshallFloyd() {mAdjacencyMatrix.warshallFloyd(mNodeNum);}const vector<vector<bool>>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); }const vector<vector<int>>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); }const vector<vector<int>>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); }const vector<vector<int>>& getPrevNodeMap() const { return mAdjacencyMatrix.getPrevNodeMap(); }private:AdjacencyMatrix mAdjacencyMatrix;};// 無向グラフ Directed Val Graph.class dvgraph : public vgraph {public:dvgraph(int nodeNum) :vgraph(nodeNum) {}void addEgde(int nodeID1, int nodeID2, int cost) {mNodes[nodeID1]->addEgde(make_shared<vegde>(mNodes[nodeID1], mNodes[nodeID2], cost));}void removeEgde(int nodeID1, int nodeID2) {mNodes[nodeID1]->removeEgde(nodeID1, nodeID2);}};// 隣接行列付きの有向グラフ。ワーシャルフロイドが使える。 Directed Val Graph Matrixclass dvgraph_m : public dvgraph {public:dvgraph_m(int nodeNum) :dvgraph(nodeNum) {mAdjacencyMatrix = AdjacencyMatrix(nodeNum);}void addEgde(int nodeID1, int nodeID2, int cost) {dvgraph::addEgde(nodeID1, nodeID2, cost);mAdjacencyMatrix.addEgde(nodeID1, nodeID2, cost);}void removeEgde(int nodeID1, int nodeID2) {dvgraph::removeEgde(nodeID1, nodeID2);mAdjacencyMatrix.removeEgde(nodeID1, nodeID2);}void warshallFloyd() {mAdjacencyMatrix.warshallFloyd(mNodeNum);}const vector<vector<bool>>& getConnectionMap() const { return mAdjacencyMatrix.getConnectionMap(); }const vector<vector<int>>& getCostMap() const { return mAdjacencyMatrix.getCostMap(); }const vector<vector<int>>& getMinimumDistMap() const { return mAdjacencyMatrix.getMinimumDistMap(); }const vector<vector<int>>& getPrevNodeMap() const { return mAdjacencyMatrix.getPrevNodeMap(); }private:AdjacencyMatrix mAdjacencyMatrix;};// 立っているビットの数を返すstatic int bitcount8(unsigned char b8) {// 8 bits 限定アルゴリズムを利用している//c_assert( 8 == (CHAR_BIT * sizeof( b8 )) );b8 = (unsigned char)( ((b8 & 0xAA) >> 1) + (b8 & 0x55) );b8 = (unsigned char)( ((b8 & 0xCC) >> 2) + (b8 & 0x33) );b8 = (unsigned char)( ((b8 & 0xF0) >> 4) + (b8 & 0x0F) );return b8;}// 立っているビットの数を返すstatic int bitcount16(unsigned short w16) {// 16 bits 限定アルゴリズムを利用している//c_assert( 16 == (CHAR_BIT * sizeof( w16 )) );w16 = (unsigned short)( ((w16 & 0xAAAA) >> 1) + (w16 & 0x5555) );w16 = (unsigned short)( ((w16 & 0xCCCC) >> 2) + (w16 & 0x3333) );w16 = (unsigned short)( ((w16 & 0xF0F0) >> 4) + (w16 & 0x0F0F) );w16 = (unsigned short)( ((w16 & 0xFF00) >> 8) + (w16 & 0x00FF) );return w16;}// 立っているビットの数を返すstatic int bitcount32(unsigned long dw32) {// 32 bits 限定アルゴリズムを利用している//c_assert( 32 == (CHAR_BIT * sizeof( dw32 )) );dw32 = ((dw32 & 0xAAAAAAAA) >> 1) + (dw32 & 0x55555555);dw32 = ((dw32 & 0xCCCCCCCC) >> 2) + (dw32 & 0x33333333);dw32 = ((dw32 & 0xF0F0F0F0) >> 4) + (dw32 & 0x0F0F0F0F);dw32 = ((dw32 & 0xFF00FF00) >> 8) + (dw32 & 0x00FF00FF);dw32 = ((dw32 & 0xFFFF0000) >> 16) + (dw32 & 0x0000FFFF);return dw32;}}using namespace ValLib;int main(){int Q;cin >> Q;vector<int> D(Q);vector<int> X(Q);vector<ull> T(Q);for (int i = 0; i < Q; ++i) {cin >> D[i] >> X[i] >> T[i];}//vmath::makePascalTriangle(3000);for (int i = 0; i < Q; ++i) {if (D[i] == 1) {if (T[i] >= 1) {cout << "AC" << endl;} else {cout << "ZETUBOU" << endl;}continue;}//if (T[i] > 1e15) {// cout << "ZETUBOU" << endl;// continue;//}// nCr -> X[i]C(D[i] - 1)の組み合わせ?順列?int n = X[i] + D[i] - 1;int r = D[i] - 1;int count = 1;ull result = 1;bool tle = false;for (int numerator = n - r + 1; numerator <= n; ++numerator) {int denominator = count;result = result * numerator / denominator;if (result > T[i]) {cout << "ZETUBOU" << endl;tle = true;break;}++count;}//ull num = vmath::combination(n, r);if (tle) {continue;}if (result <= T[i]) {cout << "AC" << endl;} else {cout << "ZETUBOU" << endl;}}getchar();getchar();}