結果
問題 | No.1665 quotient replace |
ユーザー | sapphire__15 |
提出日時 | 2021-09-03 21:56:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 889 ms / 3,000 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 1,530 ms |
コンパイル使用メモリ | 140,248 KB |
実行使用メモリ | 89,848 KB |
最終ジャッジ日時 | 2023-08-21 21:32:48 |
合計ジャッジ時間 | 29,716 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 450 ms
89,700 KB |
testcase_01 | AC | 450 ms
89,560 KB |
testcase_02 | AC | 459 ms
89,820 KB |
testcase_03 | AC | 454 ms
89,524 KB |
testcase_04 | AC | 456 ms
89,632 KB |
testcase_05 | AC | 450 ms
89,612 KB |
testcase_06 | AC | 469 ms
89,504 KB |
testcase_07 | AC | 449 ms
89,508 KB |
testcase_08 | AC | 457 ms
89,708 KB |
testcase_09 | AC | 472 ms
89,672 KB |
testcase_10 | AC | 598 ms
89,800 KB |
testcase_11 | AC | 766 ms
89,392 KB |
testcase_12 | AC | 511 ms
89,664 KB |
testcase_13 | AC | 875 ms
89,848 KB |
testcase_14 | AC | 879 ms
89,444 KB |
testcase_15 | AC | 889 ms
89,368 KB |
testcase_16 | AC | 883 ms
89,416 KB |
testcase_17 | AC | 881 ms
89,536 KB |
testcase_18 | AC | 450 ms
89,568 KB |
testcase_19 | AC | 449 ms
89,732 KB |
testcase_20 | AC | 450 ms
89,296 KB |
testcase_21 | AC | 447 ms
89,496 KB |
testcase_22 | AC | 449 ms
89,604 KB |
testcase_23 | AC | 447 ms
89,628 KB |
testcase_24 | AC | 450 ms
89,596 KB |
testcase_25 | AC | 451 ms
89,604 KB |
testcase_26 | AC | 458 ms
89,504 KB |
testcase_27 | AC | 456 ms
89,580 KB |
testcase_28 | AC | 470 ms
89,684 KB |
testcase_29 | AC | 485 ms
89,756 KB |
testcase_30 | AC | 678 ms
89,532 KB |
testcase_31 | AC | 767 ms
89,672 KB |
testcase_32 | AC | 760 ms
89,792 KB |
testcase_33 | AC | 568 ms
89,648 KB |
testcase_34 | AC | 709 ms
89,540 KB |
testcase_35 | AC | 677 ms
89,400 KB |
testcase_36 | AC | 686 ms
89,476 KB |
testcase_37 | AC | 669 ms
89,464 KB |
testcase_38 | AC | 716 ms
89,488 KB |
testcase_39 | AC | 632 ms
89,764 KB |
testcase_40 | AC | 636 ms
89,648 KB |
testcase_41 | AC | 636 ms
89,740 KB |
testcase_42 | AC | 452 ms
89,844 KB |
testcase_43 | AC | 457 ms
89,428 KB |
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <bitset> #include <climits> #include <cmath> #include <complex> #include <functional> #include <cassert> #include <stack> #include <numeric> #include <iomanip> #include <limits> #include <random> #include <unordered_map> #include <unordered_set> #include <chrono> #include <cstring> typedef long long ll; typedef std::pair<int, int> Pii; typedef std::pair<ll, ll> Pll; typedef std::pair<double, double> Pdd; #define rip(_i, _n, _s) for (int _i = (_s); _i < (int)(_n); _i++) #define all(_l) _l.begin(), _l.end() #define rall(_l) _l.rbegin(), _l.rend() #define MM << " " << template<typename _T> using MaxHeap = std::priority_queue<_T>; template<typename _T> using MinHeap = std::priority_queue<_T, std::vector<_T>, std::greater<_T>>; template<typename _T> inline bool chmax(_T &_l, const _T _b) { if (_b > _l) { _l = _b; return true; } return false; } template<typename _T> inline bool chmin(_T &_l, const _T _b) { if (_l > _b) { _l = _b; return true; } return false; } template<typename _T> void vdeb(const std::vector<_T> &bb) { for (unsigned int i = 0;i < bb.size();i++) { if (i == bb.size() - 1) std::cout << bb[i]; else std::cout << bb[i] << ' '; } std::cout << '\n'; } template<typename _T> void vdeb(const std::vector<std::vector<_T>> &bb) { for (unsigned int i = 0;i < bb.size();i++) { std::cout << i << ": "; vdeb(bb[i]); } std::cout << '\n'; } using namespace std; class Eratosthenes { std::vector<std::vector<long long>> large_sieve; std::vector<long long> small_sieve; public: const long long l; const long long r; Eratosthenes(const long long l_, const long long r_) : large_sieve(r_-l_), small_sieve(sqrt(r_)+2), l(l_), r(r_) { assert(0 < l && l < r); const long long SQ = small_sieve.size(); std::vector<long long> tmp; for(int i = 0; i < r-l; i++) { tmp.push_back(i+l); } for(long long i = 2; i < SQ; i++) { if(small_sieve[i] > 0) continue; for(long long j = i*i; j < (long long)small_sieve.size(); j += i) { small_sieve[j] = i; } for(long long j = (l+i-1)/i*i; j < r; j += i) { while(tmp[j-l]%i == 0) { large_sieve[j-l].push_back(i); tmp[j-l] /= i; } } } for(long long i = l; i < r; i++) { while(1 < tmp[i-l] && tmp[i-l] < SQ && 0 < small_sieve[tmp[i-l]]) { large_sieve[i-l].push_back(small_sieve[tmp[i-l]]); tmp[i-l] /= small_sieve[tmp[i-l]]; } if(tmp[i-l] > 1) large_sieve[i-l].push_back(tmp[i-l]); } } std::vector<long long> factorization(long long x) { assert(l <= x && x < r); return large_sieve[x-l]; } void varify() { for(long long i = l; i < r; i++) { long long now = 1; for(auto &&j : large_sieve[i-l]) { assert(1 < j); now *= j; } assert(now == i); } } }; int main() { Eratosthenes er(1, 1000100); int n; cin >> n; vector<int> da(n); rip(i,n,0) cin >> da[i]; size_t xx = 0; rip(i,n,0) { xx ^= er.factorization(da[i]).size(); } cout << (xx == 0 ? "black" : "white") << endl; }