Submission #67351141

Source Code Expand

Copy
/*
import sys 
from collections import Counter
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
T_str = sys.stdin.readline()
if T_str:
    T = int(T_str)
    for _ in range(T):
        N_str = sys.stdin.readline()
        if not N_str:
            break
        N = int(N_str)
        A = list(map(int, sys.stdin.readline().split()))
        counts = Counter(A)
        unique_vals = sorted(counts.keys())
        Nu = len(unique_vals)
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
/*
import sys 
from collections import Counter

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

T_str = sys.stdin.readline()
if T_str:
    T = int(T_str)
    for _ in range(T):
        N_str = sys.stdin.readline()
        if not N_str:
            break
        N = int(N_str)
        A = list(map(int, sys.stdin.readline().split()))
        counts = Counter(A)
        unique_vals = sorted(counts.keys())
        Nu = len(unique_vals)
        
        if Nu <= 1:
            sys.stdout.write("Yes\n")
            continue
        
        found_yes = False
        candidate_pairs = []
        
        U_abs_sorted = sorted(unique_vals, key=abs)
        
        b1_cands_group1 = {U_abs_sorted[0]}
        if -U_abs_sorted[0] in counts:
            b1_cands_group1.add(-U_abs_sorted[0])
        b2_cands_group1 = {U_abs_sorted[1]}
        if -U_abs_sorted[1] in counts:
            b2_cands_group1.add(-U_abs_sorted[1])
        
        for b1 in b1_cands_group1:
            for b2 in b2_cands_group1:
                if b1 != b2:
                    candidate_pairs.append((b1, b2))
        
        b1_cands_group2 = {U_abs_sorted[-1]}
        if -U_abs_sorted[-1] in counts:
            b1_cands_group2.add(-U_abs_sorted[-1])
        b2_cands_group2 = {U_abs_sorted[-2]}
        if -U_abs_sorted[-2] in counts:
            b2_cands_group2.add(-U_abs_sorted[-2])
        
        for b1 in b1_cands_group2:
            for b2 in b2_cands_group2:
                if b1 != b2:
                    candidate_pairs.append((b1, b2))
        
        for b1_cand, b2_cand in candidate_pairs:
            temp_counts = counts.copy()
            r_num, r_den = b2_cand, b1_cand
            common_divisor = gcd(abs(r_num), abs(r_den))
            r_num //= common_divisor
            r_den //= common_divisor
            if r_den < 0:
                r_den = -r_den
                r_num = -r_num
            current_term = b1_cand
            is_valid_sequence = True
            for i in range(N):
                if current_term not in temp_counts or temp_counts[current_term] == 0:
                    is_valid_sequence = False
                    break
                temp_counts[current_term] -= 1
                if i < N - 1:
                    next_term_num = current_term * r_num
                    if next_term_num % r_den != 0:
                        is_valid_sequence = False
                        break
                    current_term = next_term_num // r_den
            if is_valid_sequence:
                found_yes = True
                break
        
        if found_yes:
            sys.stdout.write("Yes\n")
        else:
            sys.stdout.write("No\n")
*/

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

int gcd(int a, int b) {
    while (b) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main() {
    int T;
    string T_str;
    if (getline(cin, T_str)) {
        T = stoi(T_str);
        for (int _ = 0; _ < T; ++_) {
            string N_str;
            if (!getline(cin, N_str)) break;
            int N = stoi(N_str);

            vector<int> A(N);
            for (int i = 0; i < N; ++i) {
                cin >> A[i];
            }
            cin.ignore(); // to clear newline after reading numbers

            map<int, int> counts;
            for (int a : A) counts[a]++;

            set<int> unique_vals_set;
            for (auto p : counts) unique_vals_set.insert(p.first);
            vector<int> unique_vals(unique_vals_set.begin(), unique_vals_set.end());
            int Nu = unique_vals.size();

            if (Nu <= 1) {
                cout << "Yes\n";
                continue;
            }

            bool found_yes = false;
            vector<pair<int, int>> candidate_pairs;

            vector<int> U_abs_sorted = unique_vals;
            sort(U_abs_sorted.begin(), U_abs_sorted.end(), [](int x, int y) {
                return abs(x) < abs(y);
            });

            set<int> b1_cands_group1 = {U_abs_sorted[0]};
            if (counts.count(-U_abs_sorted[0])) b1_cands_group1.insert(-U_abs_sorted[0]);
            set<int> b2_cands_group1 = {U_abs_sorted[1]};
            if (counts.count(-U_abs_sorted[1])) b2_cands_group1.insert(-U_abs_sorted[1]);

            for (int b1 : b1_cands_group1) {
                for (int b2 : b2_cands_group1) {
                    if (b1 != b2) candidate_pairs.emplace_back(b1, b2);
                }
            }

            set<int> b1_cands_group2 = {U_abs_sorted[Nu - 1]};
            if (counts.count(-U_abs_sorted[Nu - 1])) b1_cands_group2.insert(-U_abs_sorted[Nu - 1]);
            set<int> b2_cands_group2 = {U_abs_sorted[Nu - 2]};
            if (counts.count(-U_abs_sorted[Nu - 2])) b2_cands_group2.insert(-U_abs_sorted[Nu - 2]);

            for (int b1 : b1_cands_group2) {
                for (int b2 : b2_cands_group2) {
                    if (b1 != b2) candidate_pairs.emplace_back(b1, b2);
                }
            }

            for (auto [b1_cand, b2_cand] : candidate_pairs) {
                map<int, int> temp_counts = counts;
                int r_num = b2_cand, r_den = b1_cand;
                int common_divisor = gcd(abs(r_num), abs(r_den));
                r_num /= common_divisor;
                r_den /= common_divisor;
                if (r_den < 0) {
                    r_den = -r_den;
                    r_num = -r_num;
                }
                int current_term = b1_cand;
                bool is_valid_sequence = true;
                for (int i = 0; i < N; ++i) {
                    if (temp_counts[current_term] == 0) {
                        is_valid_sequence = false;
                        break;
                    }
                    temp_counts[current_term]--;
                    if (i < N - 1) {
                        long long next_term_num = 1LL * current_term * r_num;
                        if (next_term_num % r_den != 0) {
                            is_valid_sequence = false;
                            break;
                        }
                        current_term = next_term_num / r_den;
                    }
                }
                if (is_valid_sequence) {
                    found_yes = true;
                    break;
                }
            }

            if (found_yes) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
    return 0;
}

Submission Info

Submission Time
Task D - Make Geometric Sequence
User SqRooti
Language C++ 23 (gcc 12.2)
Score 425
Code Size 6776 Byte
Status AC
Exec Time 254 ms
Memory 30392 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 1
AC × 32
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 02_handmade_31.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3644 KiB
01_random_01.txt AC 60 ms 3608 KiB
01_random_02.txt AC 209 ms 22440 KiB
01_random_03.txt AC 249 ms 28528 KiB
01_random_04.txt AC 126 ms 3608 KiB
01_random_05.txt AC 148 ms 11836 KiB
01_random_06.txt AC 33 ms 3544 KiB
01_random_07.txt AC 55 ms 3976 KiB
01_random_08.txt AC 128 ms 3532 KiB
01_random_09.txt AC 126 ms 3608 KiB
01_random_10.txt AC 72 ms 3460 KiB
01_random_11.txt AC 190 ms 20100 KiB
01_random_12.txt AC 127 ms 3608 KiB
01_random_13.txt AC 126 ms 3524 KiB
01_random_14.txt AC 126 ms 3648 KiB
01_random_15.txt AC 132 ms 7236 KiB
01_random_16.txt AC 126 ms 3580 KiB
01_random_17.txt AC 126 ms 3464 KiB
01_random_18.txt AC 93 ms 3548 KiB
01_random_19.txt AC 61 ms 3928 KiB
01_random_20.txt AC 58 ms 3532 KiB
01_random_21.txt AC 194 ms 21400 KiB
01_random_22.txt AC 127 ms 3548 KiB
01_random_23.txt AC 77 ms 3648 KiB
01_random_24.txt AC 254 ms 30392 KiB
01_random_25.txt AC 127 ms 3548 KiB
01_random_26.txt AC 128 ms 3584 KiB
01_random_27.txt AC 110 ms 7852 KiB
01_random_28.txt AC 199 ms 21600 KiB
01_random_29.txt AC 127 ms 3608 KiB
01_random_30.txt AC 67 ms 7668 KiB
02_handmade_31.txt AC 1 ms 3460 KiB
Facebook Twitter Telegram Share

2025-08-22 (Fri)
02:48:36 +09:00

More…