結果
問題 | No.1665 quotient replace |
ユーザー |
![]() |
提出日時 | 2021-09-03 21:56:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,072 ms / 3,000 ms |
コード長 | 3,525 bytes |
コンパイル時間 | 2,756 ms |
コンパイル使用メモリ | 135,360 KB |
最終ジャッジ日時 | 2025-01-24 05:39:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#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; }