|

General

# 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
→ Source
#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;
}
}
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?