結果
問題 | No.946 箱箱箱 |
ユーザー | Astral__ |
提出日時 | 2023-08-01 20:27:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 364 ms / 2,000 ms |
コード長 | 7,904 bytes |
コンパイル時間 | 2,955 ms |
コンパイル使用メモリ | 226,952 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 11:36:24 |
合計ジャッジ時間 | 15,193 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 234 ms
5,248 KB |
testcase_04 | AC | 240 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 239 ms
5,248 KB |
testcase_07 | AC | 240 ms
5,248 KB |
testcase_08 | AC | 242 ms
5,248 KB |
testcase_09 | AC | 300 ms
5,248 KB |
testcase_10 | AC | 235 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 277 ms
5,248 KB |
testcase_13 | AC | 241 ms
5,248 KB |
testcase_14 | AC | 239 ms
5,248 KB |
testcase_15 | AC | 236 ms
5,248 KB |
testcase_16 | AC | 237 ms
5,248 KB |
testcase_17 | AC | 235 ms
5,248 KB |
testcase_18 | AC | 239 ms
5,248 KB |
testcase_19 | AC | 337 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 234 ms
5,248 KB |
testcase_22 | AC | 236 ms
5,248 KB |
testcase_23 | AC | 241 ms
5,248 KB |
testcase_24 | AC | 236 ms
5,248 KB |
testcase_25 | AC | 364 ms
5,248 KB |
testcase_26 | AC | 237 ms
5,248 KB |
testcase_27 | AC | 235 ms
5,248 KB |
testcase_28 | AC | 235 ms
5,248 KB |
testcase_29 | AC | 241 ms
5,248 KB |
testcase_30 | AC | 238 ms
5,248 KB |
testcase_31 | AC | 238 ms
5,248 KB |
testcase_32 | AC | 229 ms
5,248 KB |
testcase_33 | AC | 237 ms
5,248 KB |
testcase_34 | AC | 241 ms
5,248 KB |
testcase_35 | AC | 238 ms
5,248 KB |
testcase_36 | AC | 238 ms
5,248 KB |
testcase_37 | AC | 238 ms
5,248 KB |
testcase_38 | AC | 364 ms
5,248 KB |
testcase_39 | AC | 232 ms
5,248 KB |
testcase_40 | AC | 236 ms
5,248 KB |
testcase_41 | AC | 235 ms
5,248 KB |
testcase_42 | AC | 236 ms
5,248 KB |
testcase_43 | AC | 239 ms
5,248 KB |
testcase_44 | AC | 362 ms
5,248 KB |
testcase_45 | AC | 238 ms
5,248 KB |
testcase_46 | AC | 239 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
testcase_52 | AC | 2 ms
5,248 KB |
testcase_53 | AC | 2 ms
5,248 KB |
ソースコード
#include<bits/stdc++.h> #define PPque priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> #define Pque priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> #define pque priority_queue<int, vector<int>, greater<int>> #define umap unordered_map #define uset unordered_set #define rep(i, s, f) for(ll i = s; i <= f; i++) #define per(i, s, f) for(ll i = s; i >= f; i--) #define all0(x) (x).begin() ,(x).end() #define all(x) (x).begin() + 1, (x).end() #define vvvi vector<vector<vector<int>>> #define vvvl vector<vector<vector<ll>>> #define vvvc vector<vector<vector<char>>> #define vvvd vector<vector<vector<double>>> #define vvi vector<vector<int>> #define vvl vector<vector<ll>> #define vvs vector<vector<string>> #define vvc vector<vector<char>> #define vvp vector<vector<pair<ll, ll>>> #define vvb vector<vector<bool>> #define vvd vector<vector<double>> #define vp vector<pair<ll, ll>> #define vi vector<int> #define vl vector<ll> #define vs vector<string> #define vc vector<char> #define vb vector<bool> #define vd vector<double> #define P pair<ll, ll> #define TU tuple<ll, ll, ll> #define rrr(l, r) mt()%(r-1)+l+1 #define ENDL '\n' #define ull unsigned long long #define debug(a, s) rep(i, s, a.size()-1) {cout << a.at(i) << " ";}cout << endl; #define Debug(a, s) rep(i, s, a.size()-1) {rep(j, s, a.at(i).size()-1) {cout << a.at(i).at(j) << " ";}cout << endl;} typedef long long ll; using namespace std; //////////////////////////////////////////////////////////////////////////////////////////////////////////// //これが本当の組み込み関数ってね(笑) template <typename T> T or_less(vector<T> &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1); } template <typename T> T under(vector<T> &A, T x) { //x未満の最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1); } template <typename T> T or_more(vector<T> &A, T x) { //x以上で最小要素の添字 前提: sort済み 存在しない: N . //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)); } template <typename T> T over(vector<T> &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: N return distance(A.begin(), upper_bound(A.begin(), A.end(), x)); } void compress(vector<ll> &A) {//小さい順に順位、大きい順にしたいならreverseはNG最後に変換 vector<ll> temp = A; sort(temp.begin()+1, temp.end()); for (int i = 1; i <= int(A.size()-1); i++) { A.at(i) = distance(temp.begin(), lower_bound(temp.begin()+1, temp.end(), A.at(i))); } } ll LIS1(vl &A) {//at(0)は番兵、広義単調増加 ll N = A.size()-1; vl L(N+1, 1001001001001001001LL); L.at(0) = -1 * 1001001001001001001LL; ll ans = 0; rep(i, 1, N) { ll idx = over<ll>(L, A.at(i)); L.at(idx) = A.at(i); ans = max(ans, idx); } return ans; } ll LIS2(vl &A) {//狭義単調増加 ll N = A.size() - 1; vl L(N+1, 1001001001001001001LL); L.at(0) = -1 * 1001001001001001001LL; ll ans = 0; rep(i, 1, N) { ll idx = or_more<ll>(L, A.at(i)); L.at(idx) = A.at(i); ans = max(ans, idx); } return ans; } ////////////////////////////////////////////////////////////////////// //数学系 /////////////////////////////////////////////////////////////////////// ll POWER(ll a, ll b, ll mod) { a %= mod; vector<ll> pow (61); pow.at(0) = a; bitset<60> bina(b); ll answer = 1; for (int i = 1; i <= 60; i++) { pow.at(i) = pow.at(i-1) * pow.at(i-1) % mod; if (bina.test(i-1)) { answer = (answer*pow.at(i-1)) % mod; } } return answer; } ll Div(ll a, ll b, ll mod) { return a * POWER(b, mod-2, mod) % mod; } ll round(ll x, ll i) { return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i)); } template <typename T> //約分 void normalize(T &mol, T &deno) { T mol_temp = abs(mol); T deno_temp = abs(deno); T GCD = gcd(mol_temp, deno_temp); mol /= GCD; deno /= GCD; } vvl mat_mul(vvl &a, vvl &b, ll mod) {//0-indexed && 正方行列 ll n = a.size(); vvl res(n , vl(n, 0)); rep(i, 0, n-1) { rep(j, 0, n-1) { rep(k, 0, n-1) { res.at(i).at(j) += a.at(i).at(k) * b.at(k).at(j); res.at(i).at(j) %= mod; } } } return res; } vvl mat_pow(vvl &a, ll b, ll mod) {//0-indexed && 正方行列 bitset<60> bina(b); vvl power = a; int N = a.size(); vvl res(N, vl(N, 0)); rep(i, 0, N-1) { res.at(i).at(i) = 1; } rep(i, 1, 60) { if (bina.test(i-1)) { res = mat_mul(res, power, mod); } power = mat_mul(power, power, mod); } return res; } vvl comb(ll n, ll mod) {//計算にO(N^2) 読み取りにO(1) vvl v(n+1, vl(n+1, 0)); rep(i, 0, v.size() - 1) { v.at(i).at(0) = 1; v.at(i).at(i) = 1; } rep(i, 1, v.size()-1) { rep(j, 1, i) { v.at(i).at(j) = v.at(i-1).at(j-1) + v.at(i-1).at(j); v.at(i).at(j) %= mod; } } return v; } ll nCk(int n, int k, ll mod) {//毎回O(max(分子、 分母)) ll ue = 1; ll sita = 1; for (int i = 1; i <= k; i++) { sita *= i; sita %= mod; } for (int i = 1; i <= k; i++) { ue *= (n-i+1); ue %= mod; } return Div(ue, sita, mod); } ll cross(P a, P b) { return a.first * b.second - a.second * b.first; } ll nto10(string S, ll base) { ll res = 0; reverse(all0(S)); while(!S.empty()) { ll num = S.back() - '0'; if(num < 0 || num > 9) num = 9 + S.back() - 'a' + 1; res = res * base + num; S.pop_back(); } return res; } string toN(ll N, ll base) { if(N == 0) return "0"; string ans =""; ll MOD = abs(base); while(N != 0) { ll first = N % MOD; while(first < 0) first += MOD; ans += to_string(first); N -= first; N /= base; } reverse(all0(ans)); return ans; } double DIST(P a, P b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); } vp factrization(ll N) { vp res; for (int i = 2; i * i <= N; i++) { ll cnt = 0; while(N % i == 0) { cnt++; N /= i; } if(cnt != 0) res.push_back(P(i, cnt)); } if(N != 1) res.push_back(P(N, 1)); return res; } ////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //グローバル変数を置くところ(情報工学意識高め) ll int_max = 1001001001; ll ll_max = 1001001001001001001LL; const double pi = 3.141592653589793; vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1}; //#pragma GCC optimize ("-O3") //ll mod = 1000000007; //ll mod = 998244353; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void solve() { ll N; cin >> N; vl A(N+1); rep(i, 1, N) { cin >> A.at(i); } vl sum_A(N+1, 0); rep(i, 1, N) { sum_A.at(i) = sum_A.at(i-1) ^ A.at(i); } vl G(N+1, 0); per(i, N-1, 0) { set<ll> cnt; rep(j, i+1, N) { ll gran = sum_A.at(j) ^ sum_A.at(i) ^ G.at(j); cnt.insert(gran); } rep(j, 0, N) { if(!cnt.count(j)) { G.at(i) = j; break; } } } if(G.at(0) == 0) { cout << "Takanashi" << endl; } else { cout << "Takahashi" << endl; } //if(S.at(i) == 1 ← 笑) // modは取りましたか...?(´・ω・`) } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); solve(); return 0; }