justforasking's blog

By justforasking, history, 21 month(s) ago, In English

Problem : This is last round problem C.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod = 1e9+7;
 
int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(0);cout.tie(0);
 
 ll t;
 cin >> t;
 while(t--){
 ll n, m;
 cin >> n >> m;
 vector<ll>arr1(n);
 for(ll i = 0;i<n;i++)cin >> arr1[i];
 ll z;
 cin >> z;
 vector<ll>arr2(z);
 for(ll i = 0;i<z;i++)cin >> arr2[i];
 map<ll, ll>mp1, mp2;

 for(ll i = 0;i<n;i++){
    ll x = arr1[i];
    ll cnt = 1;
    while(x % m == 0){
         x = x * 1ll / m * 1ll;
         cnt = cnt * m * 1ll;
    }
    mp1[x] += cnt;
 }

 for(ll i = 0;i<z;i++){
    ll x = arr2[i];
    ll cnt = 1;
    while(x % m == 0){
        x = x * 1ll / m * 1ll;
        cnt = cnt * m * 1ll;;
    }
    mp2[x] += cnt;
 }

 if(mp1 == mp2){
    cout << "Yes" << endl;
 }
 else cout << "No" << endl;
  
 }
}

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Your solution checks for overall count of numbers, however the problem implies some segments to be consecutive. Your solution doesn't check this idea and that's why you get a wrong answer.

Example: you might have 2 2 4 2 and 4 2 2 2 your solution says YES however you can easily see that the answer is NO.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depends on the value of m. If m is 2, then this example shall still result in YES.