?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
170409697 |
Practice: invertedwinger |
1718B - 29 | C++17 (GCC 7-32) | Wrong answer on test 9 | 841 ms | 308 KB | 2022-08-31 19:47:46 | 2022-08-31 19:47:46 |
#include <iostream> #include<bits/stdc++.h> #include<algorithm> #include<vector> #include <numeric> #include<cmath> #include<iomanip> typedef long double ld; typedef long long ll; #define nl '\n' #define vi vector<int> #define vll vector<ll> #define rep(i,a,b) for(int i = (a); i < (b); i++) #define per(i,a,b) for(int i = (a); i >= (b); i--) #define repl(i,a,b) for(ll i = (a); i < (b); i++) #define perl(i,a,b) for(ll i = (a); i >= (b); i--) using namespace std; ll MOD = 1000000007; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; vll c(n); ll s = 0; rep(i,0,n){ cin>>c[i]; s += c[i]; } if(n==1){ if(c[0]==1){ cout<<"YES"<<nl; } else{ cout<<"NO"<<nl; } continue; } ll N = 2; vll f; f.push_back(1); f.push_back(1); int k = 2; while(N<s){ f.push_back(f[k-1]+f[k-2]); k++; N += f[k-1]; } if(N!=s){ cout<<"NO"<<nl; continue; } ll mx = 0; for(int i=k-1; i>=0; i-=2){ mx += f[i]; } vll cnt(k,0); int ans = 0; vi b; rep(i,0,n){ ll x = c[i]; if(x>mx){ ans = 1; break; } if(x>f[k-1]){ x -= f[k-1]; cnt[k-1]++; if(cnt[k-1]>1){ ans=1; break; } } while(x > 0){ int idx = lower_bound(f.begin(), f.end(), x) - f.begin(); if(f[idx]==x){ if(x==1){ if(cnt[1]==0){ cnt[1]++; } else if(cnt[0]==0){ cnt[0]++; } else{ ans=1; break; } } else if(idx%2==0){ cnt[idx]++; if(cnt[idx]>1){ ans=1; break; } } else{ b.push_back(idx); } x=0; break; } idx--; cnt[idx]++; if(cnt[idx]>1){ ans=1; break; } x -= f[idx]; } if(ans==1){ break; } } for(auto y:b){ if(cnt[y]==0){ cnt[y]++; } else{ for(int j=0; j<=y; j+=2){ if(cnt[j]>0){ ans=1; break; } cnt[j]++; } } } if(ans==1){ cout<<"NO"<<nl; continue; } rep(i,0,k){ if(cnt[i]!=1){ ans=1; break; } } if(ans==1){ cout<<"NO"<<nl; } else{ cout<<"YES"<<nl; } } }
?
?
?
?