結果

問題 No.2392 二平方和
ユーザー 孫悟空孫悟空
提出日時 2023-07-28 22:06:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 33,980 bytes
コンパイル時間 3,199 ms
コンパイル使用メモリ 222,384 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 18:58:46
合計ジャッジ時間 4,184 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ALL(a) (a).begin(),(a.end())
#define brep(n,hhh) for(int i=n-1;i>=hhh;i--)
#define rep(hhh,n) for(int i=hhh;i<n;i++)
#define jrep(hhh,n) for(int j=hhh;j<n;j++)
#define krep(hhh,n) for(int k=hhh;k<n;k++)
#define lrep(hhh,n) for(int l=hhh;l<n;l++)
#define rrep(i,k,n) for(int i=k;i<n;i++)
#define out(n) cout << n <<endl;
#define sot(A) sort(A.begin(),A.end())
#define rsot(A) sort(A.rbegin(),A.rend())
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vld vector<long double>
#define vpd vector<pair<double,double>>
#define vc vector<char>
#define vs vector<string>
#define vpi vector<pair<int,int>>
#define vvc vector<vector<char>>
#define vvi vector<vector<int>>
#define vvd vector<vector<double>>
#define vvpd vector<vector<pair<double,double>>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvvi vector<vector<vector<vector<int>>>>
#define vvvpi vector<vector<vector<Pi>>>
#define vvpi vector<vector<pair<int,int>>>
#define vvtpi vector<vector<tuple<int,int,int>>>
#define dout(x,y) cout<<x<<" "<<y<<endl;
#define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
#define Pi pair<int,int>
#define Pd pair<double,double>
#define Pdi pair<double,int>
#define TPi tuple<int,int,int>
#define QPi tuple<int,int,int,int>
#define FPi tuple<int,int,int,int,int>
#define TPd tuple<double,int,int>
#define spi pair<string,int>
#define pb push_back
constexpr int MOD1=1000000007;
constexpr int MOD2=998244353;
constexpr int BIG=10000000000000000;
//int BBB=ppow(2,31)-1;
class BIT {
public:
//
int n;
//
vector<int> a;
//
BIT(int n):n(n),a(n+1,0){}
//a[i]x
void add(int i,int x){
i++;
if(i==0) return;
for(int k=i;k<=n;k+=(k & -k)){
a[k]+=x;
//a[k]%=MOD2;
}
}
void conf(){
for(int i=0;i<=n;i++){
cout<<a[i]<<' ';
}
cout<<endl;
}
//a[i]+a[i+1]+…+a[j]
int sum(int i,int j){
return (sum(j)-sum(i-1));
}
//a[0]+a[1]+…+a[i]
int sum(int i){
i++;
int s=0;
if(i==0) return s;
for(int k=i;k>0;k-=(k & -k)){
s+=a[k];
//s%=MOD2;
}
return s;
}
//a[0]+a[1]+…+a[i]>=xi(ka[k]>=0)
int lower_bound(int x){
if(x<=0){
//x0→0
return 0;
}else{
int i=0;int r=1;
//
//n(BIT)
while(r<n) r=r<<1;
//調
for(int len=r;len>0;len=len>>1) {
//
if(i+len<n && a[i+len]<x){
x-=a[i+len];
i+=len;
}
}
return i;
}
}
};
class CR{
public:
vi fac;
vi finv;
vi inv;
//int MOD;
CR(int N):fac(N+1),finv(N+1),inv(N+1){
//MOD=M;
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i <= N; i++){
fac[i] = fac[i - 1] * i % MOD2;
inv[i] = MOD2 - inv[MOD2%i] * (MOD2 / i) % MOD2;
finv[i] = finv[i - 1] * inv[i] % MOD2;
}
}
//
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD2) % MOD2;
}
};//MOD
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return (int)(payload.size()) - pos; }
bool empty() const { return pos == (int)(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
}
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = (int)(pos.size());
pos.push_back({from, (int)(g[from].size())});
int from_id = (int)(g[from].size());
int to_id = (int)(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{to, to_id, cap});
g[to].push_back(_edge{from, from_id, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = (int)(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = (int)(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = (int)(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < (int)(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) break;
}
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
while (flow < flow_limit) {
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n((int)v.size()) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
struct scc_graph {
public:
scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
// @return pair of (# of scc, scc id)
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
}
struct scc_graph {
public:
scc_graph() : internal(0) {}
scc_graph(int n) : internal(n) {}
void add_edge(int from, int to) {
int n = internal.num_vertices();
assert(0 <= from && from < n);
assert(0 <= to && to < n);
internal.add_edge(from, to);
}
std::vector<std::vector<int>> scc() { return internal.scc(); }
private:
internal::scc_graph internal;
};
void conf(vs &A){
for(string i:A){
cout<<i<<' ';
}
cout<<endl;
}
void conf(vd &A){
for(double i:A){
cout<<i<<' ';
}
cout<<endl;
}
void conf(vi &A){
for(int i:A){
cout<<i<<' ';
}
cout<<endl;
}
void conf(vvvi &A,int k){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<A[i][j][k]<<' ';
}
cout<<endl;
}
}
void conf(set<int> &S){
for(int i:S)cout<<i<<' ';
cout<<endl;
}
void conf(vc &A){
for(char i:A){
cout<<i;
}
cout<<endl;
}
void conf(vvi &A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<A[i][j]<<" ";
}
cout<<endl;
}
}
void conf(vvc &A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<A[i][j];
}
cout<<endl;
}
}
void conf(vvb &A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<(int)A[i][j]<<" ";
}
cout<<endl;
}
}
void conf(vvpi &A){
rep(0,A.size()){
jrep(0,A[i].size()){
cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" ";
}
cout<<endl;
}
}
void conf(vpi &A){
rep(0,A.size()){
cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" ";
}
cout<<endl;
}
int max(int a,int b){
if(a>b)return a;
else return b;
}
int min(int a,int b){
if(a>b)return b;
else return a;
}
int modpow(int x,int n,int mod){
int res=1;
while(n>0){
int l=x%mod;
if(n&1)res=(res%mod)*l%mod;
x=l*l%mod;
n>>=1;
}
return res;
}//(mod)log(N)
int ppow(int x,int n){
int res=1;
while(n>0){
if(n&1)res=res*x;
x=x*x;
n>>=1;
}
return res;
}//log(N)
int modinv(int a, int m) {
int b = m, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}//EuClid,a,mOKmlog(a);
vi smallest_prime_factors(int n) {
vi spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (int i = 2; i * i <= n; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= n; j += i) {
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vector<int> enumdiv(int n) {
vector<int> S;
for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
sort(S.begin(), S.end());
return S;
}//vector,√N
vi soinsu(int N){
vi T;
int n=N;
int k=2;
while(k*k<=n){
if(N%k==0){
N=N/k;
T.push_back(k);
}
else{
k++;
}
}
if(N!=1)T.push_back(N);
if(T.size()==0){
T.push_back(n);
}
return T;
}//vi(sort),O(√N)
int legendre(int N,int k){
int ans=0;
int K=k;
while(N>=K){
ans+=N/K;
K*=k;
}
return ans;
}//N!k
vb Eratosthenes(int N){
vb IsPrime(N+1,true);
IsPrime[0] = false; // 0
IsPrime[1] = false; // 1
for(int i=2; i*i<=N; ++i) // 0sqrt(max)調
if(IsPrime[i]) // i
for(int j=2; i*j<=N; ++j) // (max)i
IsPrime[i*j] = false;
return IsPrime;
}//Nnloglogn
int lgcd(int A, int B){
//int a,b,C;
while (A!=0 && B!=0){
if (A>B){
//a=A/B;
A-=A/B*B;
}else{
//b=B/A;
B-=B/A*A;
}
//out(7)
}
//C=max(A,B);
return max(A,B);
}
int lcm(int a, int b) {
return a / lgcd(a, b) * b;
}
void YN(bool A){
if(A){
out("Yes");
}else{
out("No");
}
}
double max(double a,double b){
if(a>b){
return a;
}else{
return b;
}
}
double min(double a,double b){
if(a>b){
return b;
}else{
return a;
}
}
vvi mat_mul(vvi &a, vvi &b,int MOD) {
vvi res(a.size(), vi(b[0].size(),0));
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b[0].size(); j++) {
for (int k = 0; k < b.size(); k++) {
(res[i][j] ^= a[i][k]&b[k][j]);
}
}
}
return res;
}
vvi mat_pow(vvi a, int n,int MOD) {
int d=1;
vvi res(a.size(), vi(a.size()));
//
for (int i = 0; i < a.size(); i++)
res[i][i] = (d<<33)-1;
//
while (n > 0) {
if (n & 1) res = mat_mul(a, res,MOD);
a = mat_mul(a, a,MOD);
n >>= 1;
}
return res;
}
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n((v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
struct dsu {
public:
dsu() : _n(0) {}
dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
vi topological_sort(vvi &G, vector<int> &indegree, int V) {
//
vector<int> sorted_vertices;
// 0
queue<int> que;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
// 1~3
while (que.empty() == false) {
//
int v = que.front();
que.pop();
// 0
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
// v
sorted_vertices.push_back(v);
}
//
return sorted_vertices;
}
vi dikstra(int s,int V,vvpi &G){
vi d(V,BIG);
priority_queue<Pi,vector<Pi>,greater<Pi>> que;
d[s]=0;
que.push(Pi(0,s));//Pi()
while(!que.empty()){
Pi p=que.top();que.pop();
int v=p.second;
if(d[v]<p.first)continue;
rep(0,G[v].size()){
int a=G[v][i].second;
int b=G[v][i].first;
if(d[a]>d[v]+b){
d[a]=d[v]+b;
que.push(Pi(d[a],a));
}
}
}
return d;
}//0start
/*int op(int a, int b) {
return max(a,b);
}
int e() {
return 0;
}*/
//int target;
//bool f(int v) { return v >= target; }
struct loopdfs{
public:
int flgggg;
bool gg;
bool x;
int start;
loopdfs(int n){
flgggg=-1;
gg=false;
x=false;
start=n;//0-indexed
};
void loops(int a,vvi &G,vb &seen,vi &loop,vi &prev){
seen[a]=true;
for (auto nv : G[a]) {
if(gg)continue;
if (seen[nv]){
flgggg=nv;
gg=true;
x=true;
break;
}
loops(nv,G,seen,loop,prev);
}
if(!gg&&x){
prev.push_back(a);
}
if(gg){
loop.push_back(a);
}
if(flgggg==a)gg=false;
if(a==start){
reverse(loop.begin(),loop.end());
reverse(prev.begin(),prev.end());
}
}//functional graph
};
vvi calcNext(const string &S) {
int n = (int)S.size();
vector<vector<int> > res(n+1, vector<int>(26, n));
for (int i = n-1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
res[i][S[i]-'a'] = i;
}
return res;
}
struct S{
int v;
//int size;
};
S op(S a,S b){
return {min(a.v,b.v)};
}
S e(){
return {BIG};
}
S mapping(int a, S b){
return {a+b.v};
}
int composition(int a,int b){
return a+b;
}
int id(){return 0;}
vi compress(vi &A){
vi vals=A;
sot(vals);
vals.erase(unique(vals.begin(), vals.end()), vals.end());
vi X(A.size());
rep(0,A.size()){
X[i]=lower_bound(vals.begin(),vals.end(),A[i])-vals.begin();
}
return X;
}//0-indexed
template <typename T>
vector<T> compress(vector<T> &C1, vector<T> &C2,int w) {
vector<T> vals;
int N = (int)C1.size();
for (int i = 0; i < N; i++) {
for (int d = 0; d <= 0; d++) { // for (T d = 0; d <= 0; d++)
T tc1 = C1[i] - d;
if(tc1>=0){
vals.push_back(tc1);
}
T tc2 = C2[i] + d;
if(tc2<=w){
vals.push_back(tc2);
}
}
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 0; i < N; i++) {
C1[i] = lower_bound(vals.begin(), vals.end(), C1[i]) - vals.begin();
C2[i] = lower_bound(vals.begin(), vals.end(), C2[i]) - vals.begin();
}
return vals;
}//2
int kruskal(vector<TPi> &A,int V){
sot(A);
int M=A.size();
dsu uf(V+1);
int res=0;
rep(0,M){
int a=get<1>(A[i]);int b=get<2>(A[i]); int c=get<0>(A[i]);
if(!uf.same(a,b)){
uf.merge(a,b);
res+=c;
}
}
bool flag=false;
rep(1,V+1){
if(!uf.same(i,0))flag=true;
}
if(flag){
res=-1;
}
return res;
}
string encode(string& str) {
string ret = ""; //
int n=(int)(str.size());
for (int l = 0; l < n;) {
int r = l + 1;
while(r < n && str[l] == str[r]){
r++;
}
ret.push_back(str[l]);
char num_str = (char)((r - l)+'0'); //
ret += num_str;
l = r;
}
return ret;
}
bool revsort(const Pi &a,const Pi &b){
if(a.first>b.first){
return true;
}else{
if(a.first==b.first){
if(a.second<b.second){
return true;
}else{
return false;
}
}else{
return false;
}
}
}//Pifirstsecond
bool anglesortbool(const Pi &a,const Pi &b){
int x=a.first*b.second-a.second*b.first;
if(x>0){
return true;
}else{
return false;
}
}
vpi anglesort(vpi &A){
vvpi qua(4);
rep(0,A.size()){
int x=A[i].first;int y=A[i].second;
if(x>0&&y>=0){
qua[0].push_back(Pi(x,y));
}
if(x<=0&&y>0){
qua[1].push_back(Pi(x,y));
}
if(x<0&&y<=0){
qua[2].push_back(Pi(x,y));
}
if(x>=0&&y<0){
qua[3].push_back(Pi(x,y));
}
}
rep(0,4){
sort(qua[i].begin(),qua[i].end(),anglesortbool);
}
vpi B;
rep(0,4){
jrep(0,qua[i].size()){
B.pb(qua[i][j]);
}
}
return B;
}//pair1090
void dfs1(vvb &G,int h,int w,int H,int W){
if(G[h][w])return;
G[h][w]=true;
vi dh={1,0,-1,0};
vi dw={0,1,0,-1};
rep(0,4){
int x=h+dh[i];int y=w+dw[i];
if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(!G[x][y])){
//out(9);
dfs1(G,x,y,H,W); //
}
}
//A[h][w]=1;
}
void dfs(vb &seen,int a,vvi &G){
if(seen[a])return;
seen[a]=true;
for(int i:G[a]){
if(seen[i])continue;
//seen[i]=true;
dfs(seen,i,G); //
}
//A[h][w]=1;
}
template< typename T >
struct SparseTable {
vector< vector< T > > st;
vector< int > lookup;
SparseTable(const vector< T > &v) {
int b = 0;
while((1 << b) <= v.size()) ++b;
//out(b)
st.assign(b, vector< T >(1 << b));
for(int i = 0; i < v.size(); i++) {
st[0][i] = v[i];
}
//conf(st);
for(int i = 1; i < b; i++) {
for(int j = 0; j + (1 << i) <= (1 << b); j++) {
st[i][j] = lgcd(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);//
}
}
lookup.resize(v.size() + 1);
for(int i = 2; i < lookup.size(); i++) {
lookup[i] = lookup[i >> 1] + 1;
}
}
inline T gcd(int l, int r) {
//conf(st);
if(l==r){
return 0;//
}
int b = lookup[r - l];
//out(st[b][r - (1 << b)])
return lgcd(st[b][l], st[b][r - (1 << b)]);
}//
};
int bdp2(int N,int bit,vi &dp,vb &seen){
if(seen[bit]){
//out(7)
return dp[bit];
}
//out(7)
int res = dp[bit];
brep((1<<N),0){
i&=bit;
int pbit=bit&(~i);
if(i==0||pbit==0)continue;
//dout(bit,pbit)
res=min(bdp2(N,i,dp,seen)+bdp2(N,pbit,dp,seen),res);
}
seen[bit]=true;
return dp[bit]=res; //
}
vvi bfs3(vvc &G,vvi &A,int h,int w,int H,int W){
vi dh={1,0,-1,0};
vi dw={0,1,0,-1};
A[h][w]=0;
queue<Pi> que;
que.push(Pi(h,w));
while(!que.empty()){
Pi v=que.front();que.pop();
rep(0,4){
int x=v.first+dh[i];int y=v.second+dw[i];
if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(A[x][y]==-1)&&G[x][y]!='#'){
que.push(Pi(x,y));
A[x][y]=A[v.first][v.second]+1;
}
}
}
return A;
}
signed main(){
int P;cin>>P;
bool flag=false;
int k=1;
while(k*k<=P){
int x=sqrt(P-k*k);
if(k*k+x*x==P)flag=true;
k++;
}
YN(flag);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0