Участник:Morgachev/VFRIEND2

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/VFRIEND2/

C++14 (clang8.0)

#include<cstdio>
#include<iostream>
#include<algorithm>
 
 
using namespace std;
 
#define int long long
 
 
int v[10000007], n;
int csum[10000007];
 
 
int bs(int i) {
    int l = i + 1;
    int r = n, mid;
 
    while (r >= l) {
        mid = (l + r) / 2;
        if (r == l) {
            return l;
        }
 
        if (r - l == 1) {
            if (v[r] >= i) {
                return r;
            } else {
                return l;
            }
        }
 
        if (v[mid] < i) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }
    return 0;
}
 
int32_t main() {
    int32_t T;
    scanf("%d", &T);
    while (T--) {
        int n, a, b, c, m, ind, flag = 0;
        scanf("%lld %lld %lld %lld %lld", &n, &a, &b, &c, &m);
        v[1] = 0;
        for (int i = 2; i <= n; i++) {
            v[i] = ((a * v[i - 1]) + b) % m;
        }
        for (int i = 1; i <= n; i++) {
            v[i] += c;
        }
 
        sort(v + 1, v + n + 1, greater<>());
 
        csum[0] = 0;
        for (int i = 1; i <= n; i++) {
            csum[i] = v[i] + csum[i - 1];
        }
 
        if (csum[n] % 2 == 1 || csum[n] > n * (n - 1)) {
            printf("SAD\n");
            continue;
        }
 
        for (int i = 1; i < n; i++) {
            if (i >= v[i + 1]) {
                if (csum[i] > (i * (i - 1) + csum[n] - csum[i])) {
                    flag = 1;
                    printf("SAD\n");
                    break;
                }
            } else if (i <= v[n]) {
                if (csum[i] > (i * (i - 1) + i * (n - i))) {
                    printf("SAD\n");
                    flag = 1;
                    break;
                }
            } else {
                ind = bs(i);
                if (csum[i] > (i * (i - 1) + csum[n] - csum[ind] + i * (ind - i))) {
                    printf("SAD\n");
                    flag = 1;
                    break;
                }
            }
        }
        if (flag == 0) {
            printf("HAPPY\n");
        }
    }
    return 0;
}