Виктор работает в сервисе по ремонту клавиатур. Чаще всего ремонт заключается в переключении тумблера с положения OFF в ON, из-за этого Виктор уже заскучал. Но однажды ему принесли сломанную клавиатуру с неизвестной раскладкой. Виктор подключил клавиатуру к компьютеру и зашёл в текстовый редактор. Он стал нажимать различные клавиши из-за чего на экране в текстовом редакторе стали печататься неизвестные символы. Тогда Виктор использовал специальный анализатор, который напрямую считывает код нажатой клавиши, а также произвольно пронумеровал клавиши самой клавиатуры. Виктор решил, что хоть он и не знает правильной нумерации, всё равно можно оценить работоспособность клавиатуры. Для этого Виктор придумал численный коэффициент работоспособности клавиатуры. Для вычисления этого коэффициента Виктор нажимает произвольные клавиши на клавиатуре и записывает соответствующие полученные коды от анализатора. Так как правильное сопоставление неизвестно, то сравнивать номера и коды клавиш напрямую нельзя, поэтому Виктор решил анализировать нажатия попарно. Хорошей парой нажатий Виктор называет такую пару ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают и номера k i = k j , и коды c i = c j клавиш. Почти хорошая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают и номера k i ≠ k j , и коды c i ≠ c j клавиш. Плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой совпадают номера k i = k j , но не совпадают коды c i ≠ c j клавиш. Почти плохая пара нажатий — пара ( ( k i , c i ) i , ( k j , c j ) j ) , в которой не совпадают номера k i ≠ k j , но совпадают коды c i = c j клавиш. Пусть G — число хороших пар нажатий клавиш, P — число почти хороших пар, B — число плохих пар, а N — число почти плохих пар. Тогда коэффициент работоспособности клавиатуры равен: √ G + √ P √ B + √ N Если √ B + √ N = 0 , то клавиатура считается полностью рабочей, поэтому численное значение коэффициента не имеет смысл. Формат входных данных Первая строка содержит натуральное число N ( 2 ≤ N ≤ 10 5 ) — число нажатий. Вторая строка содержит N натуральных чисел k i ( 1 ≤ k i ≤ 10 9 ) — номера нажатых клавиш. Третья строка содержит N натуральных чисел c i ( 1 ≤ c i ≤ 10 9 ) — коды соответствующих клавиш. Формат выходных данных Выведите значение коэффициента работоспособности клавиатуры, либо -1, если клавиатура полностью рабочая. Ответ будет засчитан, если его абсолютная или относительная погрешность не будет превышать 10 − 9 .

Краткое объяснение задачи

• Нужно посчитать четыре типа пар между любыми двумя нажатиями:
  • Годные (G): совпадают и номера клавиш, и коды: k_i = k_j и c_i = c_j.
  • Почти хорошие (P): номера разные, коды разные: k_i ≠ k_j и c_i ≠ c_j.
  • Плохие (B): одинаковые номера, но коды разные: k_i = k_j и c_i ≠ c_j.
  • Почти плохие (N): разные номера, но одинаковые коды: k_i ≠ k_j и c_i = c_j.
• Затем коэффициент: coef = sqrt(G) + sqrt(P) / ( sqrt(B) + sqrt(N) ).
  • Если sqrt(B) + sqrt(N) = 0, клавиатура полностью рабочая → выводим -1.

Как посчитать G, B, N, P за один проход по данным

• Пусть:
  • freqK[k] — сколько раз встречается номер клавиши k.
  • freqC[c] — сколько раз встречается код c.
  • freqKC[(k,c)] — сколько раз встречается конкретная пара (k,c).
• Тогда:
  • G = сумма по всем парам (k,c) из freqKC: C(freqKC[(k,c)], 2).
  • S1 = сумма по всем k из freqK: C(freqK[k], 2).
  • S2 = сумма по всем c из freqC: C(freqC[c], 2).
  • T = C(N, 2).
  • B = S1 - G.
  • Np = S2 - G.
  • P = T - G - B - Np = T - S1 - S2 + G.
• Если B = 0 и Np = 0, выводим -1. Иначе считаем coef.

Сложности

• Время: O(N) (один проход и несколько хеш-кейсов).
• Память: O(U), где U — число уникальных k, уникальных c и уникальных пар (k,c).

Ниже приведён рабочий C++17-код.

Код (C++17)

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

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

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> k(N), c(N);
    for (int i = 0; i < N; ++i) cin >> k[i];
    for (int i = 0; i < N; ++i) cin >> c[i];

    // Частоты
    unordered_map<long long, long long> freqK;
    unordered_map<long long, long long> freqC;
    // Объединённый ключ (k,c) -> freq
    unordered_map<unsigned long long, long long> freqKC;

    freqK.reserve(N * 2);
    freqC.reserve(N * 2);
    freqKC.reserve(N * 2);

    for (int i = 0; i < N; ++i) {
        long long ki = k[i];
        long long ci = c[i];
        freqK[ki]++;
        freqC[ci]++;

        unsigned long long key = ( (unsigned long long)ki << 32 ) | (unsigned long long)ci;
        freqKC[key]++;
    }

    auto choose2 = [](long long x) -> long long {
        return x > 1 ? (x * (x - 1)) / 2 : 0;
    };

    // G: одинаковые (k,c)
    long long G = 0;
    for (auto &p : freqKC) {
        long long v = p.second;
        G += choose2(v);
    }

    // S1: по k
    long long S1 = 0;
    for (auto &p : freqK) {
        S1 += choose2(p.second);
    }

    // S2: по c
    long long S2 = 0;
    for (auto &p : freqC) {
        S2 += choose2(p.second);
    }

    long long T = (long long)N * (N - 1) / 2;

    long long B = S1 - G;
    long long Np = S2 - G; // "almost bad" (N) в условии задача
    long long P = T - G - B - Np; // или P = T - S1 - S2 + G

    // Если sqrt(B) + sqrt(Np) == 0, клавиатура полностью рабочая
    if (B == 0 && Np == 0) {
        cout << -1 << "\n";
        return 0;
    }

    long double denom = sqrt((long double)B) + sqrt((long double)Np);
    long double coef = sqrt((long double)G) + sqrt((long double)P) / denom;

    cout.setf(std::ios::fixed); 
    cout << setprecision(12) << (double)coef << "\n";

    return 0;
}

Пояснения по коду

• Для скорости используем unordered_map и объединённый ключ для пары (k,c): key = (k << 32) | c.
• Все счёты ведутся в 64-битных целых типах (long long), чтобы не переполниться.
• Финальная величина coef выводится с высокой точностью (12 знаков после запятой).