Submission #1275154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275154		vk3601h	Sirni (COCI17_sirni)	C++20	0 / 140	455 ms	5468 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    
    sort(p.begin(), p.end());
    
    set<int> visited;
    visited.insert(p[0]);
    long long total = 0;
    
    for (int i = 1; i < n; i++) {
        int x = p[i];
        int min_weight = x;
        
        // 检查是否有约数
        bool has_divisor = false;
        for (int d = 1; d * d <= x; d++) {
            if (x % d == 0) {
                if (visited.count(d)) {
                    has_divisor = true;
                    break;
                }
                if (d != 1 && visited.count(x / d)) {
                    has_divisor = true;
                    break;
                }
            }
        }
        
        if (has_divisor) {
            visited.insert(x);
            continue;
        }
        
        // 找小于x的最大数
        auto it = visited.lower_bound(x);
        if (it != visited.begin()) {
            --it;
            int candidate = *it;
            min_weight = min(min_weight, x % candidate);
        }
        
        // 找最大的p ≤ x/2
        it = visited.upper_bound(x / 2);
        if (it != visited.begin()) {
            --it;
            int candidate = *it;
            min_weight = min(min_weight, x % candidate);
        }
        
        total += min_weight;
        visited.insert(x);
    }
    
    cout << total << endl;
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14