Cod sursa(job #3237279)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 8 iulie 2024 08:30:11
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
/**
 *    author:  Cyb3rBolt
 *    created: 07.07.2024
**/
#include <bits/stdc++.h>
#include <float.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
///Eu sunt un mic omulet de 1.80m. Numele meu este David. Am descoperit in viata asta ca imi place sa stau, sa fac la info, dar cel mai mult imi place de Iris.
///Asa ca draga mea Iris, daca cumva ajunge mesaju asta la tine sa stii ca esti ff frumoasa si ca Te iubesc!
using namespace std;
ifstream fin("cf.in");
ofstream fout("cf.out");
//#define int __int128
//#define int long long
int tt, n, a[100010], b[100010], auxA[100010], auxB[100010];

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define ll long long
#define middle (l + r) / 2
#define pb push_back
#define mp make_pair
#define pr pair<int, int>

inline int read() {
    int x = 0, m = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') m = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * m;
}

inline void write(int x) {
    if(x < 0) {
        putchar('-');
        write(-x);
        return;
    }
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}

inline void solve() {
    unordered_map<int, int> mapa;
    for(int i=1; i<=n; i++) mapa[b[i]] = i;
    int cntSchimbari = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] != b[i]) {
            cntSchimbari++;
            int index = mapa[a[i]];
            swap(b[i], b[index]);
            mapa[b[index]] = index, mapa[a[i]] = i;
        }
    }
    if(cntSchimbari % 2 == 0) cout << "YES\n";
    else cout << "NO\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> tt;
    while(tt--) {
        cin >> n;
        for(int i=1; i<=n; i++) cin >> a[i], auxA[i] = a[i];
        for(int i=1; i<=n; i++) cin >> b[i], auxB[i] = b[i];
        sort(auxA+1, auxA+n+1), sort(auxB+1, auxB+n+1);
        bool ok = true;
        for(int i=1; i<=n && ok; i++)
            if(auxA[i] != auxB[i]) ok = false;
        if(!ok) cout << "NO\n";
        else solve();
    }

    return 0;
}

/*
    for(int i=1; i<=1; i++) solOriginala++;
    for(int i=1; i<=1; i++) solOriginala--;
*/