C++

Forum

 
Code getting WA in 2 test cases although my approach is right

closed account (4z86RXSz)
Write your question here.
You are given two arrays A = A1,A2,…,AN and B = B1,B2,…,BN. We want to make these two arrays identical. That is, for each 1≤i≤N, we want to make Ai = Bi. To do this, we are allowed to make many operations of the following type:

In a single operation, we choose two integers x and y, and replace all the occurrences of x in both the arrays with y. This operation is denoted by (x,y). Notice that regardless of the number of characters replaced, it will still be counted as a single operation.

A sequence of operations ((x1,y1),(x2,y2),…,(xm,ym)) is said to be optimal, if after performing these operations in the given order, both arrays A and B are identical, and there is no sequence with fewer operations which can achieve the same.

You will also be given an integer K which will either be 1 or 2. If K=1, you need to output the minimum number of operations needed to make the two arrays identical. If K=2, in addition to the minimum number of operations, you should also output the number of different optimal sequences. As this number could be huge, output it modulo 109+7.

Input:
The first line of the input contains a single integer, T, which is the number of testcases. The description of each testcase follows.
The first line of each testcase contains two integers: N, and K.
The next line contains N integers: A1,A2,…,AN.
The next line contains N integers: B1,B2,…,BN.
Output:
You need to output a single line for each testcase.
If K=1, then that corresponding line should contain a single integer, which is the minimum number of operations needed.
If K=2, then that corresponding line should contain two integers, the minimum number of operations needed and the number of optimal sequences modulo 109+7.
Constraints
1≤T≤5
1≤N≤105
1≤K≤2
1≤Ai,Bi≤N
Subtasks
16 points : K=1
84 points : No further constraints.
Sample Input:
2
5 1
2 1 1 3 5
1 2 2 4 5
5 2
2 1 1 3 5
1 2 2 4 5
Sample Output:
2
2 8
Explanation:
Testcase 1: The arrays are initially (2,1,1,3,5) and (1,2,2,4,5). Consider the sequence of operations ((1,2),(3,4)). In the first operation all the 1s are converted into 2s. So, the arrays will now be (2,2,2,3,5) and (2,2,2,4,5). In the second operation all the 3s are converted into 4s. So, the arrays will now be (2,2,2,4,5) and (2,2,2,4,5). We have made the two arrays identical in two operations, and you can check that you cannot do better. Hence the output is 2.

Testcase 2: The arrays are the same, and hence the first integer is the same. Now we need to also find the number of optimal sequences. They are listed below:

((1,2),(3,4))
((1,2),(4,3))
((2,1),(3,4))
((2,1),(4,3))
((3,4),(1,2))
((3,4),(2,1))
((4,3),(1,2))
((4,3),(2,1))
Since there are eight optimal sequences, the second integer is 8.
1
2
3
4
5
6
7
8
 
  Put the code you need help with here.
To solve this i
first made array a contain all the smaller element with respect to b

now made a set and inserted the unique pairs
then displayed the count of unique pair

implementation of my code is below


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mod 1000000007
ll power(ll x,ll y, ll p)
{
    ll res = 1;      // Initialize result
    x = x % p;  // Update x if it is more than or
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}
ll modFact(ll n, ll p)
{
    if (n >= p)
        return 0;

    ll result = 1;
    for (ll i = 1; i <= n; i++)
        result = (result * i) % p;

    return result;
}
int main()
{
    SPEED;
    //Code
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m1;
        cin>>n>>m1;
        ll a[n];
        for(int i=0;i<n;i++)
        cin>>a[i];
        ll b[n];
        for(int i=0;i<n;i++)
        cin>>b[i];
        for(int i=0;i<n;i++)
        {
            if(a[i]>b[i])
            {
                ll temp=a[i];
                a[i]=b[i];
                b[i]=temp;
            }
        }
        set<pair<ll,ll>> m;
        ll z=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]!=b[i])
            {
                m.insert(make_pair(a[i],b[i]));
            }
        }
        if(m1==1)
            cout<<m.size()<<endl;
        else if(m1==2)
        {
            ll g=m.size();
            ll h=(modFact(g,mod)*power(2,g,mod))%mod;//h=optimal sequences
            cout<<g<<" "<<h<<endl;
        }
    }
    return 0;
}
tpb (1495)
If you're going to use:

1
2
 
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); // untie cin from cout


then you definitely don't want to cout << endl (which flushes the stream). Use cout << '\n' instead (which generally only flushes if it outputs to a terminal). And note that cout << '\n' is faster than cout << "\n" (although the latter may be optimized to the former). The latter dereferences a pointer and then loops to output a null-terminated string; the former outputs a single character.

Also, std::cout.tie(0) doesn't do anything since by default, cout is not tied to anything (i.e., std::cout.tie() returns nullptr).
Last edited on
closed account (4z86RXSz)
cool thanks
Topic archived. No new replies allowed.