結果
問題 | No.973 余興 |
ユーザー | drken1215 |
提出日時 | 2020-01-18 20:29:36 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,314 ms / 4,000 ms |
コード長 | 3,346 bytes |
コンパイル時間 | 798 ms |
コンパイル使用メモリ | 81,400 KB |
実行使用メモリ | 199,508 KB |
最終ジャッジ日時 | 2023-09-10 11:32:15 |
合計ジャッジ時間 | 66,909 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,779 ms
199,492 KB |
testcase_01 | AC | 1,763 ms
199,128 KB |
testcase_02 | AC | 1,743 ms
199,220 KB |
testcase_03 | AC | 1,728 ms
199,200 KB |
testcase_04 | AC | 1,790 ms
199,264 KB |
testcase_05 | AC | 1,783 ms
199,156 KB |
testcase_06 | AC | 1,791 ms
199,496 KB |
testcase_07 | AC | 1,734 ms
199,128 KB |
testcase_08 | AC | 1,754 ms
198,688 KB |
testcase_09 | AC | 1,784 ms
199,472 KB |
testcase_10 | AC | 1,694 ms
191,876 KB |
testcase_11 | AC | 591 ms
73,928 KB |
testcase_12 | AC | 580 ms
73,764 KB |
testcase_13 | AC | 598 ms
73,228 KB |
testcase_14 | AC | 585 ms
73,404 KB |
testcase_15 | AC | 44 ms
10,900 KB |
testcase_16 | AC | 44 ms
11,384 KB |
testcase_17 | AC | 25 ms
8,056 KB |
testcase_18 | AC | 33 ms
9,788 KB |
testcase_19 | AC | 33 ms
9,620 KB |
testcase_20 | AC | 25 ms
7,756 KB |
testcase_21 | AC | 43 ms
10,900 KB |
testcase_22 | AC | 43 ms
11,068 KB |
testcase_23 | AC | 34 ms
9,660 KB |
testcase_24 | AC | 33 ms
9,316 KB |
testcase_25 | AC | 15 ms
5,968 KB |
testcase_26 | AC | 25 ms
8,348 KB |
testcase_27 | AC | 56 ms
12,260 KB |
testcase_28 | AC | 33 ms
9,608 KB |
testcase_29 | AC | 33 ms
9,520 KB |
testcase_30 | AC | 1,946 ms
199,168 KB |
testcase_31 | AC | 1,946 ms
199,500 KB |
testcase_32 | AC | 1,930 ms
199,324 KB |
testcase_33 | AC | 1,941 ms
199,212 KB |
testcase_34 | AC | 1,935 ms
198,600 KB |
testcase_35 | AC | 1,952 ms
199,160 KB |
testcase_36 | AC | 1,914 ms
194,264 KB |
testcase_37 | AC | 1,896 ms
194,312 KB |
testcase_38 | AC | 2,001 ms
198,636 KB |
testcase_39 | AC | 1,998 ms
199,092 KB |
testcase_40 | AC | 1 ms
4,380 KB |
testcase_41 | AC | 1 ms
4,380 KB |
testcase_42 | AC | 2 ms
4,376 KB |
testcase_43 | AC | 2 ms
4,380 KB |
testcase_44 | AC | 2 ms
4,380 KB |
testcase_45 | AC | 2 ms
4,380 KB |
testcase_46 | AC | 1,930 ms
199,508 KB |
testcase_47 | AC | 1,979 ms
199,164 KB |
testcase_48 | AC | 1,981 ms
199,128 KB |
testcase_49 | AC | 1,794 ms
183,960 KB |
testcase_50 | AC | 2,314 ms
197,812 KB |
testcase_51 | AC | 1,947 ms
199,160 KB |
testcase_52 | AC | 1,948 ms
199,200 KB |
testcase_53 | AC | 1,960 ms
195,728 KB |
testcase_54 | AC | 1,953 ms
199,324 KB |
testcase_55 | AC | 1,954 ms
199,356 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template <class Abel> struct BIT { const Abel UNITY_SUM = 0; // to be set vector<Abel> dat; /* [1, n] */ BIT(int n) : dat(n + 1, UNITY_SUM) { } void init(int n) { dat.assign(n + 1, UNITY_SUM); } /* a is 1-indexed */ inline void add(int a, Abel x) { for (int i = a; i < (int)dat.size(); i += i & -i) dat[i] = dat[i] + x; } /* [1, a], a is 1-indexed */ inline Abel sum(int a) { Abel res = UNITY_SUM; for (int i = a; i > 0; i -= i & -i) res = res + dat[i]; return res; } /* [a, b), a and b are 1-indexed */ inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); } /* debug */ void print() { for (int i = 1; i < (int)dat.size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; int N; long long X; vector<long long> a, s; vector<int> l2r, r2l; bool solve() { l2r.assign(N+1, -1), r2l.assign(N+1, -1); int r = 0; for (int l = 0; l < N; ++l) { while (r < N && s[r + 1] - s[l] <= X) { ++r; r2l[r] = l; } l2r[l] = r; } //COUT(l2r); COUT(r2l); vector<BIT<int> > left(N+5, BIT<int>(N+5)); vector<BIT<int> > right(N+5, BIT<int>(N+5)); for (int l = 0; l <= N; ++l) left[l].add(l+1, 1); for (int r = 0; r <= N; ++r) right[r].add(r+1, 1); for (int bet = 1; bet <= N; ++bet) { for (int l = 0; l+bet <= N; ++l) { int r = l+bet; // l+1, ..., min(l2r[l], r) に「負け」があれば OK int mi = min(l2r[l], r); int tmp1 = (mi-l) - right[r].sum(l+2, mi+2); // max(l, r2l[r]), ..., r-1 に「負け」があれば OK int ma = max(l, r2l[r]); int tmp2 = (r-ma) - left[l].sum(ma+1, r+1); // judge if (tmp1 + tmp2) left[l].add(r+1, 1), right[r].add(l+1, 1); //cout << l << ", " << r << ": " << (left[l].sum(r+1, r+2) ? "win" : "lose") << endl; } } /* for (int l = 0; l <= N; ++l) { COUT(l); cout << "sente: "; sente[l].print(); cout << "gote: "; gote[l].print(); } */ return left[0].sum(N+1, N+2); } int main() { while (cin >> N >> X) { a.resize(N); s.assign(N+1, 0); for (int i = 0; i < N; ++i) cin >> a[i], s[i+1] = s[i] + a[i]; if (solve()) cout << "A" << endl; else cout << "B" << endl; } }