1714E - Add Modulo 10 - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
 
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define piis            pair<string,string>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
#define convertToInt(x) stoi(x,nullptr,10)
#define toString(num)   to_string(num)
#define all(v)          v.begin(), v.end()
#define x               real()
#define y               imag()     
#define pi              3.1415926535897932384626
#define MAXN            1e7

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef pair<int,int>U;
typedef pair<int,pair<int,int> >T;
typedef complex<double> point;

const int mod = 1e9 + 7;

int arr[100001];
int sgmTree[400004];
vector<int>parent,sz;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
bool numericCompare(piis a,piis b)
{
    string key1,key2;
    key1=a.second;
    key2=b.second;

    return convertToInt(key1)<convertToInt(key2);
}
bool lexicoCompare(piis a,piis b)
{
    string key1,key2;
    key1=a.second;
    key2=b.second;

    return key1<key2;
}

vector<int> cumSum(vector<int>v)
{
    vector<int>cs(v.size()+1,0);
    int sum=v[0];
    int i;
    for(i=1;i<v.size();i++)
    {
        cs[i]=sum;
        sum+=v[i];
    }
    cs[i]=sum;
    return cs;
}




/************************NUMBER THEORY************************/

//finds factors in root(n) time
vector<int> factors(int n) 
{
    vector<int> f;
    for (int s = 2; s*s <= n; s++) 
    {
        while (n%s == 0) 
        {
            f.push_back(s);
            n /= s;
        }
    }
    if (n > 1) f.push_back(n);
    return f;
}

//finds factors in log2(n)+log3(n)+...... time
map<int,int> primeFact(int n)
{
    map<int,int>factors;
 
    while (n%2 == 0) 
    { 
        factors[2]++;
        n = n/2; 
    } 
 
    for (int i = 3; i <= sqrt(n); i = i+2) 
    { 
        while (n%i == 0) 
        { 
            factors[i]++;
            n = n/i; 
        } 
    } 
    
    if (n > 2) 
        factors[n]++;
 
    return factors;
 
}
int multiply(int a,int b,int m)
{
    return ((a%m)*(b%m))%m;
}
int add(int a,int b,int m)
{
    return ((a%m)+(b%m))%m;
}
int subtract(int a,int b,int m)
{
   int ans=((a%m)-(b%m))%m;
 
   if(ans<0)
    ans+=m;
 
   return ans;
}
 

int binpow(int a, int b,int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = ((res%m) * (a%m))%m;
        a = (a * a)%m;
        b >>= 1;
    }
    return res;
}
int divide(int a,int b,int m)
{
   return multiply(a,binpow(b,m-2,m),m);
}
vector<bool> sieveOfErastosthenes(int n)
{
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i*i <= n; i++) 
    {
        if (is_prime[i]) 
        {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

vector<int> sieve()
{
    vector<int>spf(MAXN,0);

    spf[1] = 1;
    for (int i=2; i<MAXN; i++)
        spf[i] = i;
  
    for (int i=4; i<MAXN; i+=2)
        spf[i] = 2;
  
    for (int i=3; i*i<MAXN; i++)
    {
      
        if (spf[i] == i)
        {
            for (int j=i*i; j<MAXN; j+=i)
                if (spf[j]==j)
                    spf[j] = i;
        }
    }

    return spf;
}
vector<int> getFactorization(int s,vector<int>spf)
{
    vector<int> ret;
    while (s != 1)
    {
        ret.push_back(spf[s]);
        s = s / spf[s];
    }
    return ret;
}


int gcd(int a, int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

int lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}

int fib(int n) 
{
  double phi = (1 + sqrt(5)) / 2;
  return round(pow(phi, n) / sqrt(5));
}

int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
vector<int> phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i - 1;

    for (int i = 2; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
              phi[j] -= phi[i];

    return phi;
}
/****************ENDING NUMBER THEORY PART********************/



int maxElement(vector<int>v)
{
    int maxEl=v[0];

    for(int i=0;i<v.size();i++) maxEl=max(maxEl,v[i]);

    return maxEl;
}
int formula(int n) 
{
    return (n*(n-1))/2;
}
 
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,  
                                            int p)
{
    return binpow(n, p - 2, p);
}
 
// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
                                 int r, int p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;
 
    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;
 
    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}
int nCr(int n,int r)
{
    //fast nCr
    if(n<0||r<0||n<r) return 0;

    int num=1;
    int denom=1;
    if((n-r)<r) r=(n-r);

    if(r!=0&&n!=0)
    {
        while(r)
        {
            num*=n;
            denom*=r;

            int toDivide=gcd(num,denom);

            num/=toDivide;
            denom/=toDivide;

            n--;
            r--;
        }
    }

    else num=1; 

    return num;
}
    int binSearch(vector<int>arr,int l,int r,int x)
    {
        while (l <= r) { 
            int m = l + (r - l) / 2; 
    
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
    
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
    
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
    
        // if we reach here, then element was 
        // not present 
        return -1;
    }


/****************************DISJOINT SET UNION********************/

void make_set(int v) 
{
    parent[v] = v;
    sz[v] = 1;
}
int find_set(int v) 
{
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) 
{
    a = find_set(a);
    b = find_set(b);
    if (a != b) 
    {
        if (sz[a] < sz[b])
            swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}

/****************************DISJOINT SET ENDING********************/


void c_p_c()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}


string solve()
{
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];

    int phase1 = 0;
    int phase2 = 0;
    int mod0 = 0, mod5 = 0;
    for(auto el : a)
    {
        int num = el;
        int lastDig = el % 10;
        num /= 10;
        int secondLastDig = num % 10;
        bool flag = false;
        if((10 - secondLastDig) & 1)
            flag = true;

        if(lastDig == 0)
            mod0++;
        else if(lastDig == 5)
            mod5++;
        else if(lastDig == 1 or lastDig == 2 or lastDig == 4 or lastDig == 8)
        {
            if(flag)
                phase2++;
            else
                phase1++;
        }
        else if(lastDig == 3 or lastDig == 6)
        {
            if(flag)
                phase1++;
            else
                phase2++;
        }
        else if(lastDig == 7 or lastDig == 9)
        {
            if(flag)
                phase1++;
            else
                phase2++;
        }

        if((phase2 > 0 and phase1 > 0) or ((mod0 > 0 or mod5 > 0) and (phase2 > 0 or phase1 > 0)))
            return "No";
    }  

    if(mod0 == 0 and mod5 == 0)
        return "Yes";
    else
    {
        map<int, int>freq1, freq2;
        for(auto el : a)
        {
            if(el % 10 == 0)
                freq1[el]++;
            else if(el % 5 == 0)
                freq2[el]++;
        }
        if(freq1.size() > 1 or freq2.size() > 1)
            return "No";
        if((freq1.size() == 0 and freq2.size() > 0) or (freq1.size() > 0 and freq2.size() == 0))
            return "Yes";
        int num1 = (freq1.begin()) -> first;
        int num2 = (freq2.begin()) -> first;
        if(num1 - 5 != num2)
            return "No";
    } 
    return "Yes";
}

int32_t main()
{
    c_p_c();

    w(t)
    {
        cout << solve() << endl;
    }
    
    return 0;
}