Unikal ID#11853

Unikal ID (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Biz əlaqənin BİR-İKİ-ÜÇ olduğunu yoxlamalıyıq, yəni hər bir string tək bir tam ədəd üçün istifadə olunur və hər bir tam ədəd dəqiq bir string üçün istifadə olunur, bu, dəstlər və xəritələr ilə edilə bilər.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


void solve() {
    int n;cin>>n;
    //hər string yalnız bir şey üçün istifadə olunur
    //və ID tək bir fərqli string üçün istifadə olunur
    map<string,set<int>>a;
    map<int,set<string>>b;
    while(n--){
        string s;cin>>s;
        int x;cin>>x;
        a[s].insert(x);
        b[x].insert(s);
    }
    string ans="BƏLİ";
    for(auto i:a){
        if(i.second.size()>1){
            ans="XƏTA";
        }
    }
    for(auto i:b){
        if(i.second.size()>1){
            ans="XƏTA";
        }
    }
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;cin>>T;
    while (T--) solve();
    return 0;
}

C++

Çətinlik $O (n lo g n)$ \mathcal{O}(n \log n)